Would this function be o(n) time complexity?

Question

I'm currently in a data structures class, would this function be considered O(N)? My thinking was due to the while loop not having a direct correlation to the for loop, it's still O(N)? If more information/code is needed for better context, I don't mind editing the post.

I appreciate any clarification.

input_array = [7, 3, 4, 1, 8]
new_min_heap = []

for index in range(0, len(input_array)):
  val = input_array[index]

  new_min_heap.append(val)

  # if new_min_heap has other values, start swappin
  if len(new_min_heap) > 1:
    
    parent_index = get_parent_index(index)
    parent_val = new_min_heap[parent_index]

    while val < parent_val:
        new_min_heap.swap(index, parent_index)

        val = parent_val
        parent_index = get_parent_index(parent_index)
        parent_val = new_min_heap[parent_index]

Why is it a `while` and not an `if`? It looks like once you swap variables you'd break out of the `while` loop unless there is something interesting in _"# more stuff done here"_. — Selcuk, Mar 10 '21 at 05:39

score 2 · Answer 1 · answered Mar 10 '21 at 09:28

I assume the n is the size of the input array.

The for loop has the O(n) complexity since it is executed n times. The inner while loop exchanges the values between the current array element and it's ancestors. It is executed at most lg(n) times, so the complexity is O(lg(n)). Thus, the total complexity is O(n lg(n)).

score -1 · Answer 2 · answered Mar 10 '21 at 05:43

-1

If with "swap value and parent_value", you mean:

value, parent_value = parent_value, value

Then, the while loop will be O(1) (in case there isn't any other loop inside the while loop)

So the whole function will be O(n) based on the array length

Maybe if you bring us more context the answer could change.

answered Mar 10 '21 at 05:43

erellont

1
1

Note that in the while loop you are checking the current index with the other ones "behind" and keep swapping till you cant swap anymore because the before one is smaller than the actual one. So in the worst case (input array is ordered descendent) you have to run the while loop based on the length of the new_min_heap array. I think this is O(nlog(n)) – erellont Mar 10 '21 at 06:03
thanks, I'm trying to convert this into O(n), this is the second iteration and I thought I was onto something but, seemingly I'm not – chris Mar 10 '21 at 06:09
1

There isn't any sort algorithm (of numbers) that can run in O(n). Check this out https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm – erellont Mar 10 '21 at 06:13

Would this function be o(n) time complexity?

2 Answers2