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

Can I put a + sign in a folder with IIS?

asp.net internet-explorer iis url-rewriting url-routing

I'm pretty sure this can't be done, but I'm looking for a hack or way to put a + in a folder name, like

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.