CODEWITHSUNDEEP
pythonbig-o
Bad-Buddha
Bad-Buddha

Reputation: 23

Is this code in O(n) or O(n²)? (Python Code)

Our Professor gave us this Code as an example for the big-O notation O(n). But I wonder why. In my opinion is this code in O(n²). I hope you can help me.

def g(n):
     x = n
     y = 1
     while x > 0:
          x = x - 1
          y = y + n
     while y > 0:
          y = y - 1
     return True

I thought a code is in O(n²), when I have a loop inside a loop. This code shows two seperate loops, so it should be O(2n), but I can ignore the constants and I got O(n). Please, correct me if I´m wrong.

Thanks for your help!

Upvotes: 0

Views: 187

Answers (5)

Nick Vitha
Nick Vitha

Reputation: 476

def g(n):
     x = n           # x = n
     y = 1
     while x > 0:    
          x = x - 1  # loop through x times (since x=n, n times) 
          y = y + n  # in the end, y = (1 + n) + ((1+n) + n) + (((1+n) + n) + n) ... = n + n*n
     while y > 0:    # loops n + n^2 number of times
          y = y - 1
     return True

As you can see, it's because the value of y ends up being n + n^2, so O(n^2) is the time complexity.

Upvotes: 0

Ahmed Hammad
Ahmed Hammad

Reputation: 3095

It seems like you're just confused with python's indentations.

Those two loops are not nested!, the second loop will start only when the first loop finishes, which normally has the complexity of the summation of both loop

In other words, the first loop will take O(N), as x will reach 0 in n loops. The second loop will take O(N^2), as y will have the value of n^2 at the beginning of second loop.

Therefore, the total complexity will be O(N + N^2), and as you probably know, Big-Oh neglects minor terms, so we will end up with O(N^2).

Upvotes: -2

Bill K
Bill K

Reputation: 62789

In Python, o(n^2) would look more like this:

def g(n):
    x = n
    y = 1
    while x > 0:
        x = x - 1
        y = y + n
        while y > 0:
            y = y - 1
 return True

It's the nested loops that make it n^2, not the fact that there are two loops, and in Python nesting is indicated by indenting.

Upvotes: -1

blhsing
blhsing

Reputation: 106883

The complexity of your code is O(n^2) because y will always end up being n * n from the first loop, which adds n to y for n times, so the second loop will iterate over n * n times.

Upvotes: 0

Kevin
Kevin

Reputation: 76234

The first loop is O(N). It runs a number of times proportional to the size of n.

The second loop runs a number of times proportional to the size of y. Since y equals n**2 at the start of the loop, that makes it O(N^2).

Since the function contains an O(N) loop and an O(N^2) loop, the function is O(N^2) in total.

Upvotes: 5

Related Questions