CODEWITHSUNDEEP
pythonpython-3.xbig-ocomplexity-theory
xing Zì
xing Zì

Reputation: 411

Is the big O runtime of my function N^2 or N log N?

from linkedlist import LinkedList

def find_max(linked_list): #  Complexity: O(N)
  current = linked_list.get_head_node()
  maximum = current.get_value()
  while current.get_next_node():
    current = current.get_next_node()
    val = current.get_value()
    if val > maximum:
      maximum = val
  return maximum

def sort_linked_list(linked_list):  # <----- WHAT IS THE COMPLEXITY OF THIS FUNCTION?
  print("\n---------------------------")
  print("The original linked list is:\n{0}".format(linked_list.stringify_list()))
  new_linked_list = LinkedList()

  while linked_list.head_node:
    max_value = find_max(linked_list)
    print(max_value)
    new_linked_list.insert_beginning(max_value)
    linked_list.remove_node(max_value)

  return new_linked_list

Since we loop through the while loop N times, the runtime is at least N. For each loop we call find_max, HOWEVER, for each call to find_max, the linked_list we are parsing to the find_max is reduced by one element. Based on that, isn't the runtime N log N?

Or is it N^2?

Upvotes: 0

Views: 1087

Answers (3)

Green Cloak Guy
Green Cloak Guy

Reputation: 24691

Don't forget, O-notation deals in terms of worst-case complexity, and describes an entire class of functions. As far as O-notation goes, the following two functions are the same complexity:

64x^2 + 128x + 256           --> O(n^2)
x^2 - 2x + 1                 --> O(n^2)

In your case (and your algorithm what's called a selection sort, picking the best element in the list and putting it in the new list; other O(n^2) sorts include insertion sort and bubble sort), you have the following complexities:

0th iteration: n
1st iteration: n-1
2nd iteration: n-2
...
nth iteration: 1

So the entire complexity would be

n + (n-1) + (n-2) + ... + 1  =  n(n+1)/2  =  1/2n^2 + 1/2n

which is still O(n^2), though it'd be on the low side of that class.

Upvotes: 0

Paweł Bęza
Paweł Bęza

Reputation: 1425

It's n + n-1 + n-2 + ... + 1 which is arithmetic sequence so it is n(n+1)/2. So in big O notation it is O(n^2).

Upvotes: 4

ShadowRanger
ShadowRanger

Reputation: 155487

It's still O(n²); the reduction in size by 1 each time just makes the effective work n * n / 2 (because on average, you have to deal with half the original length on each pass, and you're still doing n passes). But since constant factors aren't included in big-O notation, that simplifies to just O(n²).

For it to be O(n log n), each step would have to halve the size of the list to scan, not simply reduce it by one.

Upvotes: 4

Related Questions