Why is the complexity of this nested for loop not $O(n^2)$? I have the following pseudo-code:

mystery(n):
if n &lt;= 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)$?
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.