Re: time complexity

See I could think of this not sure if it is right......

code is

======================
h=n;

while ( h > 0)
{
for( i=0; i<h; i++)
printf("something here");
h /= 2;
}
======================

Here it will become a series like this.
first iteration ----- n
second ------ n/2

like this but this will contine till LOG(n) base 2 terms ??
so

sum will become n + n/2 + n/4 + ..........
log(n) terms.

Formula is
a(1-pow(r,N)) / 1 - r here a is n r is 1/2 and N is logn base 2
if you computer this it gives 2(n-1).. so for n =8 -> 14 .. giving the
complexity as O(n) only.

Is this correct ??
Hope this was the homework :-)

Regards,
Gaurav

.

Relevant Pages