Komplexität eines Algorithmus

[Unkownsyntax]

Hallo hab da ein Problem und wollte sicher gehn ob es so stimmt wie ich mir das denke:

Und zwar es geht um diesesn Algorithmus:

alg(in int n) { 
 int a=... // Konstante (unabhängig von n) 
 int i=2 
 while (i <= a) { 
  int j=1 
  while (j <= n) { 
   for (k = 1..j) { 
    write(↓k) 
   } 
   j = j*2; 
  } 
  i = i*2; 
 } 
}

Und ich soll hier die asymptotische Laufzeitkomplexität in Abhängigkeit von n herausfinden.

Also ich dachte die ist n*log(n)^2 da die zwei while schleifen halbiert werden immer also logn und die for schleife linear ausgeführt wird oder?

lg daniel

 

[SlaterB]

Java-Tags?!

a ist konstant, a führt dazu, dass die innere while-Schleife 10x oder 1000x mal oder 10^99x ausgeführt wird,
aber das ist für jedes a letztlich ein konstanter Faktor, also zu ignorieren,
bleib ein log(n),

nun ist es aber so, dass nicht für jeden der log(n)-while-Fälle genau n Aktionen ausgeführt werden,
sondern auch 1, 2, 4, 8 .. n,
das scheint mir weniger als n, n, n, n .. n,
vielleicht ergeben die innere while + for zusammen log(n)^2 oder sonst eine greifbare Formel,
kann mir das grad nicht gut vorstellen,

du könntest auf jeden Fall noch einen Testdurchlauf machen, wieviele Aktionen kommen für n=1000, 10.000, 100.000 usw raus