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

Question

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?

Answer 1

It is still O(N^2)  because you are just reducing one element in each iteration. So we are doing total O(N * N / 2), but since, we don't consider constants in complexity analysis it's still O(N * N) which is O(N^2). For it to be O(NlogN) you have to halve the list in each iteration of the nested loop.