Determining the big-O of three nested for loops with if statment

user_17412088 0
Viewed 135

What is the big-O for the following code :

y=1;
x=3;

for(int i =1 ; i < =n ; i*=2)
   for(int j =1; j<= i * i; j++)
      if (i % j == 0)
         for(int k = 1; k<=j; k++) 
            y=y*x;

My Thoughts : Looking at another similar questions I think the inner most loop is O(n) and the first loop is O(log (n))..as for the middle its O(n^2)

so the overall result would be O(log(n)*n^3)

Is my answer and way of thinking right ? I'm new to this so i hope i can get some help explaning how this loops work.

nested-loops big-o time-complexity algorithm
1 Answers

the most inner loop will run j time if i % j == 0. As the middle loop will run i^2 times, only when j < i it will be possible to satisfy the specified condition. Hence, among i^2 iteration of the middle loop, at least i^2 - i times, the condition will not be satisfied.

Suppose we denote the number of divisors of i with tau(i), among j < i only tau(i) times the condition will satisfy that means the total complexity of the most inner loop is equal to the sum of divisions of i which is at most 77/16 i (see this post for the proof).

Hence, the total complexity of the middle loop with the inner loop is at most (i^2 - i) + (i - tau(i)) + 77/16 i = i^2 + 77/16 i - tau(i).

We also know that the tau(i) is in O(i^(1/loglog(i))) (see the proof here). Now, to find the complexity of the whole loop, we need to sum the last expression for i = 1, 2, 4, ..., n. As we desire to find the asymptotic complexity and we have a sum here, we can ignore the lower powers of i. Therefore, the time complexity of the whole loop is 1 + 2^2 + (2^2)^2 + ... + (2^2)^log(n) = ((2^2)^(log(n)+1)-1)/(2^2-1) = Theta(n^2) (a geometric sum with factor of 2^2 and log(n) items).

In sum, the higher time complexity analysis for the specified code is Theta(n^2) which is also in O(n^2) as well.

user_37688710
Related