Zlożoność obliczeniowa algorytmóe

Mam dwa algorytmy:

// k - zadana kwota, x=0 - wynik
// N - zbior (tablica o dlugosci l)
// nominalow

while (k>0)
{
int n=0;
for (int i=0;i<l;++i)
if((N[i]<=k)&&(N[i]>n)) n=N[i];
k -= n;
++x;
}

#define INFINITY 2147483647
typu integer
/*
...
*/

• a - liczba nominałów, k - żądana * kwota
  int T[k+1];
  T[0] = 0;
  for (int i=1;i<=k;++i) T[i]=INFINITY;
  for (int i=1;i<=a;++i)
  {
  int n;
  scanf("%d",&n);
  for (int j=0;j<=k-n;++j)
  if (T[j] < INFINITY)
  if (T[j]+1 < T[j+n])
  T[j+n] = T[j]+1;
  }

Proszę pomóżcie określić mi ich złożoność obliczeniową!?

to są algorytmy do wydawania reszty w najmniejszej liczbie monet.

pierwszy to zachłanny nie zawsze dający poprawne wyniki algorytm o złożoności O(l * x). pętla jest wykonywana x razy (0 < x < k). wynik w x.

drugi to dynamik który dla każdej kwoty od 0 do k oblicza optymalne rozwiązanie (są to optymalne podstruktury). tutaj złożoność to O(a * k) gdyż dla każdego nominału aktualizujemy (w przybliżeniu) całą tablicę. rozwiązanie w t[k].

Bardzo, bardzo dziekuje :)