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?

Answers


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.


Need Your Help

How to nest two scrollableview android with titanium

android scroll titanium

I got a little worried because I'd like a nested scrollableview but his work was his clammy.

Input .csv data (float & strings) matrix in C++

c++ csv input

I have wrote the following C++ input function. It takes a .CVS file and returns a matrix (type vector &lt; vector&lt; double&gt;&gt;). It only works for numerical values in the .CSV file, because it