time complexity

Question

What is the time complexity of the following program?

main()
{
 i = n;

while(i>=1)

  {

       i=i/2;

       i=i/3;

       i=i/5;

       i=i*10;

       i=i-10;

}

}
I am getting actual answer as  $\log _3n$+ n/10 = O(n).
Please explain briefly.

Comments

i am getting value as

1+ ⌈ log₃ ^{$(\frac{n-15}{45} )$} ⌉

by taking the T(n) = T($\frac{n-30}{3}$) + 1, where n⋗30 otherwise 1

 

for asymptotic notation ===> O(log₃ⁿ )

---

main() {
 i = n;
while(i>=1)
  {
       $\left ( \frac{i}{30}\times 10 \right ) or \left ( \frac{i}{3} \right )$
       i=i-10;
 }
}

Answer 1

Let's study your code

while(i>=1)

  {

       i=i/2;

       i=i/3;

       i=i/5;

       i=i*10;

       i=i-10;

}

the expression i=i/2,i=i/5 and i=i*10 will together get nullify

So I can rewrite your code as

while(i>=1)

  {

      

       i=i/3;

     

       

       i=i-10;

}

Now, the running time depends on how the sub-problem size decreases every time.

Initially it will be n.

After $1^{st}$ iteration it will be  $\frac{n}{3}-10$

After second iteration it will be $\frac{ \frac {n}{3}-10}{3}-10$ = $\frac{n}{3^2}-10(1+\frac{1}{3})$

So, after $K^{th}$ iteration your problem size would be

$\frac{n}{3^k}-10(1+\frac{1}{3}+\frac{1}{3^2}+......+\frac{1}{3^{k-1}})$

Simplfiy this and you will get

$\frac{n}{3^k}-10(\frac{1-\frac{1}{3^k}}{1-\frac{1}{3}})$

and this becomes $\frac{n}{3^k}+15(1-\frac{1}{3^k})$

For purpose of complexity, you can ignore the term $15(1-\frac{1}{3^k})$ as it will be a constant

So, the loop will terminate when $\frac{n}{3^k}=1$ which makes k=$\log_3n$

So your complexity is $O(log_3n)$

Comments

for i = i/3;    $\rightarrow$ time complexity should be $log_3n$ (here it is division so). check once whether am i right or wrong?

---

Yes, And since by dividing the sub problem you get very large decrements in compare to using minus(-), you can ignore the effect of minus all together

---

@ Ayush Upadhyaya, even though you did wrong at summation of G.P. , your answer is right.

 

and moreover, you can't ignore the term 5(1−3^k) as a constant due to 3^k is depend upon n... if you correctly did a Summation of G.P. you will get 5(1-$\frac{1}{3^k}$) which will lead to a constant.