Calculate and justify the time complexity of the following function:
int f(int n)
{
     int j = 10 ;
     while (j < n) {
          j += sqrt(j);
     }
     return j;
}


Difficulty level
This exercise is mostly suitable for students
We observe that j has to increase from a constant value to n, and in each iteration of the while loop, the value of j increases by at least 1 and by at most sqrt(n).  
Therefore, clearly, the time complexity of this algorithm has to be between O(n) and O(sqrt(n)).
We claim that the time complexity is O(sqrt(n)).
We can analyze separate phases of the while loop in terms of the value of j.
For the value of j to go from n/4 to n, we require at most n/sqrt(n/4)), that is 2 sqrt(n) steps.  
For the value of j to go from n/16 to n/4 , we require at most n/4 sqrt(n/16) , that is, sqrt(n) steps.   
Similarly, for the value of j to go from n/64 to n/16 , we require at most n/16(sqrt(n/64)), that is sqrt(n)/2 steps.
Therefore, overall, for the value of j to go from 1 to n, we require at most sqrt(n) (2 + 1 + 1/2+ 1/4 + ... ) = 4 sqrt(n) steps.
Therefore, the total time taken by the algorithm is O(sqrt(n)).

Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Target sum in a BST