Calculating time complexity of Python while loop

Question

I have been working on DSA problems and have also been trying to calculate the time and space complexity of my solutions. I feel like I can do ok with most solutions, however there are many, like the one below, that stump me.

    while paymentTotal <= k:
        temp = heapq.heappop(heap)
        if paymentTotal + temp > k:
            break
        paymentTotal += temp
        toyCount += 1

In this case the loop seems to be able to be broken down into this (heap is a minHeap that contains random ints. k is also a random int):

k = n
p = 0
while p <= k:
     t = heap.heapqpop(heap)
     p += t

So this would mean that the loop runs while p+t <= k, but because t does not increment p in a consistent manner and k is random I am having a hard time conceptualizing what this time complexity would be. The amount of times the loop runs obviously changes based on what k is and also what ints are popped from the heap, but I am lost on how to express that mathematically and in Big O.

Think of the worst case, when the value popped is always 1 (assuming zero is not possible). — jarmod
– jarmod, Commented Sep 22, 2022 at 15:45
Would this mean the worst case would be O(n) since it would have to run k+1 times? — dSisk
– dSisk, Commented Sep 22, 2022 at 15:56
@dSisk Worse: heappop itself is O(lg n), not O(1), in the worst case. — chepner
– chepner, Commented Sep 22, 2022 at 16:18
That's right. I keep forgetting that heapq is lg n for push and pop. — dSisk
– dSisk, Commented Sep 22, 2022 at 16:56

tzaman · Accepted Answer · 2022-09-22 16:16:29Z

1

The question to ask yourself is always "what's the worst case scenario?" Imagine an evil genie picking all your inputs to make things go as slow as possible.

In this case, k itself is a red herring, the only thing that matters is the size of the heap since with large enough k you'll have to pop the entire thing -- so that's your N (heap size). (You'll also notice that your program will raise an IndexError when that happens since you haven't accounted for that possibility.)

Errors aside, it's clear to see the loop will run N times, once for each element in the heap, and each time it will do a pop operation which is lg N, yielding N lg N as your final worst-case complexity.

One sanity-check for this result is realizing that you can sort a list by heapifying it and then popping all the elements, so it tracks with every other comparison-based sorting algorithm.

edited Sep 22, 2022 at 16:16

answered Sep 22, 2022 at 15:57

tzaman

48k11 gold badges93 silver badges118 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kelly Bundy · Accepted Answer · 2022-09-22 16:44:59Z

0

That's an output-sensitive algorithm, so take that into account accordingly: It's O(toyCount × log(|heap|)).

answered Sep 22, 2022 at 16:44

Kelly Bundy

28k7 gold badges34 silver badges76 bronze badges

Collectives™ on Stack Overflow

Calculating time complexity of Python while loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related