What is the time-complexity of this nested for loop?
I have the following code in python:
def mystery(n): if n <= 50 : for i in range(n) : for j in range(n) : print i*j else : mystery(n-1)
For the following nested for loop:
for i in range(n) : for j in range(n) :
For every i in n, j iterates through n as many as i times. So shouldn't the complexity be O(n^2)? However, my peers tell me it is not, can someone provide an explanation as to why?
Those loops are only executed when n <= 50, so they're just a concise description of a nontrivial but constant amount of work. At most 2500 print statements are executed. 2500, like any constant, is irrelevant for asymptotic complexity. Only the behavior in the limit (i.e. as n grows without bound) is important.
For larger n, the function just counts down from n down to 50. That part takes O(n) time, hence the time complexity of mystery as a whole is linear.