What is the run time complexity of this for loop?

Spark2.0

I am trying to find out the run-time complexity of this algorithm.

public static void main(String[] args) throws InterruptedException{

  for (int N=100; N<=1000000; N=N*5) {  
   long start = System.currentTimeMillis();
   for (int i = 1; i <= N; i++) {     
      for (int j = 1; j <= Math.pow(N,1.5); j++) {
      i = i*2;
      j = j*2;
      Thread.sleep(10); 
     } 
    }
   long stop = System.currentTimeMillis();
   long elapsed = (long)(stop - start);
   System.out.println();
   System.out.println("For N=" + N + " RT in msec: "+elapsed); 
 }
}

The first for loop:

for (int N=100; N<=1000000; N=N*5) // runs n/5 times, so O(n). 

The first inner loop:

for (int i = 1; i <= N; i++) // runs n times. 

The second inner loop:

for (int j = 1; j <= Math.pow(N,1.5); j++) { // we can consider Math.pow O(1)
      i = i*2;
      j = j*2;
      Thread.sleep(10); 
     } 

So by multiplying all O(n) * O(n) * O(1) = O(n^2) Is my answer correct? I am a little confused on this. Will appreciate any clarification on this. Thank You

OmG

The first loop is actually O(k) which 5^k = N. Hence, k = log_5(N). The first inner loop is true (in O(n)). And the second inner loop j is each time is times to 2. Hence, it is O(h) which 2^h = N^1.5. Therefore, h = 1.5 log(N).

In sum, the algorithm is in O(log_5(N) * N * log(N)) = O(N log^2(N)).

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

What is the time complexity of this loop?

What is the time complexity for this loop

What is the run time complexity of this code?

What is the time complexity of this while loop?

What is the time complexity of this for loop nested in a while loop?

Run time complexity for Two for loops in One for loop

What is the time complexity of the following nested loop dependency?

What is the time-complexity of this for-loop?

What will be the time complexity of a for loop nested 2 times?

What is the time-complexity of this nested for loop?

what is the Time Complexity of a nested loop in a recursive function?

What is the time complexity for a nested loop in this case?

What is time complexity of for loop of multiple conditions

What is the time complexity of this function? (nested for loop)

what is time complexity of 2 for loop written in one loop

What is the time complexity of this loop where it only runs one time?

Analysis of run time complexity

What is the Big-O Time complexity of this recursive call with a for-loop

What is the time complexity of this algorithm where the limit is changing inside the loop?

What is the Time Complexity (Big-O) of a .replace() within a while loop?

What is Big O notation (Time Complexity) of non nested for and while loop?

Time complexity of this while loop:

A while loop time complexity

Finding time complexity of this loop?

Time Complexity of This Loop

Time complexity nested loop

Time complexity with log in loop

time complexity of a double for loop

Time complexity of loop