Time Complexity for Log rquestions

Question

void fun()
{
   int i, j;
   for (i=1; i<=n; i++)
      for (j=1; j<=log(i); j++)
         printf("GeeksforGeeks");
}

Soln--> thetha(nlogn)

 

Anyone please explain me in detail how to solve log series problems and what are the prerequisites to solve log problems.As i get Stuck in log problems.Please Help!

 

Thanks

Answer 1

First thing you need to watch solving these type of problems is,

see whether loop variables are independent or dependent

now as in this qsn we see inner loop  is depending on outer loop variable i

Inner loop when i=1 in worst case can execute log1 times

inner loop when i=2  in  worst case can execute log2 times

....similarly upto n

you will have series like this-log1+log2+log3+log4+log5+log6+.......logn=lo(1*2*3.......*n)=log(n!)

now you should know that log(n!)<=O(nlogn)

so your answer would be nlogn

Comments

Hi Shubham,

I understood your solution ..Nicely explained
Can you please explain this solution for the same question.
Explanation: For i = 1, the inner loop is executed n times.
For i = 2, the inner loop is executed approximately n/2 times.
For i = 3, the inner loop is executed approximately n/3 times.
For i = 4, the inner loop is executed approximately n/4 times.
…………………………………………………….
…………………………………………………….
For i = n, the inner loop is executed approximately n/n times.

So the total time complexity of the above algorithm is (n + n/2 + n/3 + … + n/n)

Which becomes n * (1/1 + 1/2 + 1/3 + … + 1/n)

The important thing about series (1/1 + 1/2 + 1/3 + … + 1/n) is, it is equal to Θ(Logn). So the time complexity of the above code is Θ(nLogn).

Thanks

---

@mayan prakash

yes exactly brother...!

---

@shubham

Can you please explain how inner and outer loop frequency is calculated .

I did not understand that solution

---

@mayanprakash

inner loop depends on outer loop variable i..so value of i will control frequency of inner loop

when i value =1, inner loop j can be executed max log1 times similarly for evry value of i inner loops executes logi times

so there is series formed here you dont need to see how many time i loop is running if inner loop would not have depend on outer loop variable i than its frequency would hve come in picture...

here the series you will get i.e.log1+log2+....logn takes in for every value of i...

do read one time solution more you will surely get it.!