Calculating the time complexity of nested loop

Question

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++)

Answer 1

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).

Answer 2

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).

• Juan Lopes: Also known as O(n sqrt n)
• PRCube: I thought it was the other way around. outer loop is O(N) and inner loop is O(N^2). Can you justify your answer please, I would like to understand it.
• user1726343: @sasha Could you explain why the inner loop would run in O(sqrt(N))?
• user1726343: @PRCube There was some weird formatting bug where the < symbol was truncating the rest of the line. Hopefully the updated answer is clearer.