-1

What is the time complexity of this algorithm?

while len(array) > 0:
   for item in array:
      do stuff to determine which item to pop
   array.pop(item_to_pop)

My first instinct is O(N^2). However, if I were to reduce the array size by half each time the while condition executed it would be O(n). I'm guessing reducing my array size by 1 each iteration does not have the same effect?

jowens818
  • 3
  • 1
  • Welcome to SO! `do stuff to determine which item to pop` is pretty vague. What's the time complexity of this? Is the determination of the item to pop somehow fixed to the end of the list by some constant factor, or could the item be anywhere in the list? More information seems necessary here. – ggorlen Apr 05 '21 at 01:11
  • It ends up doing N(N/2) loops, which is O(N^2). `array.pop` is a relatively expensive operation. If you're filtering, it can often be more efficient to build up a new list from your old data. – Tim Roberts Apr 05 '21 at 01:11
  • This is a variation of the classic traveling salesperson problem. In this case I'm using a greedy algorithm... But yes, I'm building a new list item by item with the values I pop from the original list. At the end I will need a list of the same size as the initial one, but optimized by the 'do stuff' pseudo code. I did think about rearranging the original list each time, but I'm not sure if that would be more efficient than pop – jowens818 Apr 05 '21 at 19:33

1 Answers1

0
  • If you are reducing the size of the array by one in the outer loop, then there are n iterations in the outer loop and for each outer loop iteration, there is a maximum of n inner-loop iteration. So, by simple time complexity calculation, this is O(n^2) process.
    [n + n-1 + n-2 + .... + 1 = n(n-1)/2]
  • If you reduce the array size by half at every time in the outer loop, then there are a maximum of log(n) iterations. And for each outer loop, there are a maximum of n inner loop iteration. So, time complexity is O(n log(n)).
    [n + n\2 + n\4 + .... n(lg(n)) ~= 2n ~= 2^(lg(n)+1) ]
nipun
  • 672
  • 5
  • 11