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?

Answer 1

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, c2, c3, ..., clogc(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 / c2, n / c3, ..., , n / clogc(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, 2c, (2c)c = 2c2, (2c2)c = 2c3, ..., 2clogc(log(n)). The last term has to be less than or equal to n, and we have 2clogc(log(n)) = 2log(n) = n, which justifies the value of our last term. So there are in total logc(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, n1/c, (n1/c)1/c = n1/c2, n1/c3, ..., n1/clogc(log(n)), so there are in total logc(log(n)) iterations and each iteration takes time O(1), so the total time complexity is O(log(log(n))).