Asymptotische Laufzeit bestimmen

Neue Frage »

Auf diesen Beitrag antworten »
Rambo95 Asymptotische Laufzeit bestimmen

Meine Frage:
Hallo, ich habe folgenden Pseudocode:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
digit = 1 

for ( i=0 to n ) 
   for ( j=i to n ) 
      count = n 

      while ( count > 0 ) 
      digit = digit +1 
      count = count / 2 
 
return digit


Die asymptotische Laufzeit ist gesucht.

Meine Ideen:
Für die ersten beiden for-Schleifen ist die Laufzeit O(n)=n, da in der zweiten Schleife j=i.

Aber bei der while-Schleife denke ich, dass es O(n)=log(n) ist, da count immer halbiert wird.

Somit O(n)=n^2 * log(n) ?

Liege ich damit richtig?
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »