Time Complexity

Question

What is the time complexity of the following code?

for(i=n;i>=1;)

i=i/2;

Answer 1

Code snippet will generate given gemoetric equation-:

$f\left ( n \right )=\frac{n}{2^{0}}+\frac{n}{2^{1}}+\frac{n}{2^{2}}+...1 $

$=\frac{n}{2^{0}}+\frac{n}{2^{1}}+\frac{n}{2^{2}}+...\frac{n}{2^{k}}$

$\text{where }2^{k}=n,k=\log_{2} n$

 

$=n (1 \times \frac{1-(\frac{1}{2} )^{k+1}}{1-\frac{1}{2}})$

$=2n -\frac{n}{2^{k+1}}\approx n \text{i.e}    O(n)$

Answer 2

As we are dividing by 2 everytime so it’s log n base 2

Comments

@Eira Arora,Can you please work out your steps please?

---

n/2^1

n/2^2

n/2^3

so, further it is equals n/2^k

so it’s log(n) base 2

Answer 3

Here you can easily see that " i " is starting from " n " and going upto 1 and further adding to it the value " i " is divided by 2 every time.

So let  say that n=2^4  so how many times the loop will get executed i.e log(n) times.

Basically when the loop controlling variable gets divided or multiplied by a number the complexity goes to log(n) to the base of that number

Comments

@Phlegmatic,Could you please elaborate your steps please?