Time complexity of two separate nested while loops

user_13790342 0
Viewed 624

I just started my data structures course and I'm having troubles trying to figure out the time complexity in the following code:

{
  int j, y; 
  for(j = n; j >= 1; j--)
  { 
     y = 1; 
     while (y < j)
       y *= 2;
     while (y > 2) 
     y = sqrt(y); 
}

The outer 'for' loop is running n times in every run of the code, and the first 'while' loop runs about log2(j) if I'm not mistaken.
I'm not sure about the second 'while' loop and how to determine the overall time complexity of the code.
My initial thoughts were to determine which 'while' loop would "cost" more in each iteration of the 'for' loop, consider only the higher of the two and sum it up but obviously it didn't lead me to an answer.

Would appreciate any help, especially in what is the the process and overall approach in trying to compute the complexity in codes such as this one.

structure data-structures time-complexity
1 Answers

You are right that the first while loop has time complexity O(log(j)). The second while loop repeatedly executes square root on y until it's less than 2.

Since y is approximately j (it's between j and 2j), the question is: how often can you perform a square root on j until you get a number less than or equal to 2? But equivalently you could ask: how often can you square 2 until you get a number larger than or equal to j? Or as an equation:

    (((2^2)^...)^2 >= j    // k repeated squares
<=>        2^(2^k) >= j
<=>              k >= log(log(j))

So the second while loop has time complexity O(log(log(j)). That's negligible compared to O(log(j)). Now since j <= n and the loop is itereated n times, we get the overall complexity O(n log(n)).

user_6899230
Related