CODEWITHSUNDEEP
algorithmtime-complexity
PRCube
PRCube

Reputation: 586

Calculating the time complexity of nested loop

I'm practising with time complexity of algorithms and I came across the below code which confused me. Generally, I'm able to tell the complexity of an algorithm by looking at the number of loops, but the below code decays that hypothesis because there are two loops which I would normally assume the complexity is O(N^2) but in the second loop the N is squared. Which brings me to the conclusion that the complexity is O(N) * O(N^2) = O(N^3). Am I doing something wrong here?

for (int i = 0; i*i < N; i++)
   for (int j = 0; j*j < N*N; j++)

Upvotes: 1

Views: 1885

Answers (2)

Asad Saeeduddin
Asad Saeeduddin

Reputation: 46628

The outer loop will run while i^2< N, or equivalently while i< sqrt(N). This means the outer loop will run sqrt(N) times.

The inner loop will run while j^2< N^2, or equivalently while j< N. This means the inner loop will run N times (for each iteration of the outer loop).

The total number of iterations is therefore (N^0.5)*N=N^(3/2).

Upvotes: 3

John Feminella
John Feminella

Reputation: 311436

This has time complexity O(n sqrt(n)) = O(n^(3/2)).

  • The outer loop requires O(sqrt(n)) time. It finishes after ~sqrt(n) iterations since i grows as its square, whereas N only grows linearly.

For example, consider N = 100; i^2 takes on the values 1, 4, 9, 16, ..., 100, which is sqrt(N) distinct values. So this is O(sqrt(n)).

  • The inner loop requires O(n) time -- taking the square root of both j and N at each step should make it clear that this is a linear loop.

For example, consider N = 10; j^2 takes on the values 1, 4, 9, 16, ..., 100, which is N distinct values. So this is O(n).

Upvotes: 4

Related Questions