[Solved]: Why is the complexity of this nested for loop not $O(n^2)$?

Problem Detail: 

I have the following pseudo-code:

mystery(n): if n <= 50 :     for i = 1 ... n :         for j = 1 ... n :             print i*j else :     mystery(n-1) 

For the following nested for loop:

for i = 1 ... n :         for j = 1 ... n : 

For every i in n, j iterates through n as many as i times. So, why is it that the complexity is not $O(n^2)$?

Asked By : Bolboa

Answered By : user340082710

Because $n$ is bounded by $50$, which is simply a constant. Observe that when $n$ is larger than $50$, you simply have a recursive call. It's only when $n \leq 50$ that you go into the first portion of the if statement and execute the for-loops. Therefore, both nested loops take $\Theta(1)$ time. Hence the total time complexity of the mystery function is linear.

Note that $O(n^2)$ is technically correct, though not tight since $O(1) \subset O(n^2)$. The exact running time is $\Theta(1)$ as pointed above.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37595

3.2K people like this

 Download Related Notes/Documents