CODEWITHSUNDEEP
javaruntime
user13
user13

Reputation: 391

Determine the runtime of the function:

public static void p2(int N) { 
  for (int i = 0; i < N; i += 1) { 
    for (int j = 1; j < N; j = j * 2) {  
        System.out.println("hi !"); 
    } 
  } 
}

Can you help me to determine the runtime of this function?

I have tried to find some pattern for different inputs of N. I calculated costs for inputs up to 5 (println was used for this purposes):

N: 0, 1, 2, 3, 4, 5

C(N): 0, 0, 2, 6, 8, 15

Where C(N) is the cost function.

However, I don't know how to proceed next! The answer is Θ(N log(N))

Upvotes: 0

Views: 126

Answers (1)

abdulwasey20
abdulwasey20

Reputation: 837

The inner loop is going to execute lg n times. You can understand this by looking at how many times will you divide N by 2 to get 1? (i.e. how many times is the inner loop going to execute?) The answer to this is lg n. And the outer loop will be running N times. So for each iteration of i , the inner loop will run lg n times. Which means that the nested loop will run exactly n(lgn) times which is the time complexity of this question.

Upvotes: 4

Related Questions