2
$\begingroup$

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)$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Should be O (n), since you do make n-50 recursive calls. $\endgroup$
    – gnasher729
    Nov 29, 2016 at 19:28
  • $\begingroup$ I did say "Hence the total time complexity of the mystery function is linear." $\endgroup$ Dec 5, 2016 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.