Karumanchi

Question

what is the time complexity of

function(int n)

{

         if(n<=1) return;

         for(int i=1; i<n; i++)

         {

                     printf("*");

         }
                     function(0.8n);

         

}

i'm getting O(nlogn base 5/4) using the recurrence relation method but in the book it's given O(n)

$T(n)=T(\frac{4n}{5})+O(n)$

Comments

how is the recurence relation T(n)=T(4n/5)+O(n);

when clearly the loop is going from 1 to n and for each value of n we are calling the function(.8n);

shouldn't it be T(n)=nT(.8n)+n;

---

@sandygate I've corrected the question. this was the original question

---

ok....now it is O(n).

Answer 1

Using the recurrence, you should get it as $O(n)$.

After $k$ iterations, this is what the recurrence would look like:

$T(n) = T((\frac{4}{5})^k n) + cn(1 + 4/5 + 16/25  + \dots + (\frac{4}{5})^k)$

$\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\leq T((\frac{4}{5})^k n) + cn(1 + 4/5 + 16/25  + \dots \infty)$

which is an infinite GP with $a = 1$ and $d = 4/5$.

Therefore, your recurrence becomes:

$T(n) = 1 + 5cn$ which is $O(n)$

Comments

Can you please explain, how you got this line no. 3?

---

The original summation was from 0 to k. However, we know that the summation will converge (have a finite value.) as it is a GP with a common difference which is less than one. Hence, we can take the summation from 0 to infinity and it is bound to be greater than the original one as we are summing to a higher value than k.

I hope this was clear.

---

Actually, the solution isn't still clear.

Can you please solve it from scratch on a page and upload the same.

It will be really kind of you.

I can solve it easily by the master's theorem but I want to understand this by the method you have used.

---

The main crux of the statement is that $\sum_{0}^{k} \leq \sum_{0}^{\infty}$ which is fairly obvious as in the second number, we are summing to a number which is larger than $k$. Hence, we can use that as an upper bound.