in Algorithms edited by
1,166 views
0 votes
0 votes
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)$
in Algorithms edited by
by
1.2k views

5 Comments

log1 base 0.8 = 0

d=1==> d>log1 base 0.8

so its O(n^1) =O(n)

 

0
0
it will be 0(n)
0
0
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;
0
0

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

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

1 Answer

0 votes
0 votes
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)$
by

4 Comments

edited by
Can you please explain, how you got this line no. 3?
0
0
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.
0
0
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.
0
0
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.
0
0