TIme complexity of various nested for loops

Question

Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.

loop 1 ----

 for (int i = 1; i <=n; i *= c) 
{
   // some O(1) expressions
}

loop 2 -----

  for (int i = n; i > 0; i /= c) 
 {
   // some O(1) expressions
 }

Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.

Here c is a constant greater than 1

loop 3 ----

for (int i = 2; i <=n; i = pow(i, c)) 
{ 
    // some O(1) expressions
}

loop 4 -----

 ////Here fun is sqrt or cuberoot or any other constant root
 for (int i = n; i > 0; i = fun(i)) 
{ 
   // some O(1) expressions
}

Can anyone explain me why it is by considering the number of times the inner loop executes in these loops?

If c=1 in loop 1 and loop 2 then it will run infinite times right but it is given as logarithimic time why?

how is it O(loglogN) in loop 3 and loop 4?

chiwangc chiwangc · Accepted Answer · 2015-06-12T04:14:05

If c=1 in loop 1 and loop 2 then it will run infinite times right but it is given as logarithimic time why?

Yes you are right, if c = 1 then we will get infinite loops for both case 1 and case 2, so the condition "c is a[n integer] constant greater than 1" is also necessary for both case 1 and case 2 in order to get the O(log n) complexity.

For case 1, note that i takes values 1, c, c², c³, ..., c^log_c(n), so there are in total log(n) many iterations, and for each iteration there is a constant amount of work to be done (i.e. O(1) amount of work), so the total amount of work done is log(n) * O(1) = O(log(n)).

Similarly for case 2, i takes values n, n / c, n / c², n / c³, ..., , n / c^log_c(n), so there are in total log(n) many iterations and each iteration takes constant amount of time, so the total time complexity is O(log(n)).

For case 3, i takes values 2, 2^c, (2^c)^c = 2^c², (2^c²)^c = 2^c³, ..., 2^{c^{log_c(log(n))}}. The last term has to be less than or equal to n, and we have 2^{c^{log_c(log(n))}} = 2^log(n) = n, which justifies the value of our last term. So there are in total log_c(log(n)) many iterations, and each takes a constant amount of time to run, therefore the total time complexity is O(log(log(n))).

Similarly for case 4, i takes values n, n^1/c, (n^1/c)^1/c = n^1/c², n^1/c³, ..., n^{1/c^{log_c(log(n))}}, so there are in total log_c(log(n)) iterations and each iteration takes time O(1), so the total time complexity is O(log(log(n))).

TIme complexity of various nested for loops

1 Answers