CODEWITHSUNDEEP
pythontime-complexitybig-o
dSisk
dSisk

Reputation: 25

Calculating time complexity of Python while loop

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.

Upvotes: 2

Views: 72

Answers (2)

Kelly Bundy
Kelly Bundy

Reputation: 27588

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

Upvotes: 0

tzaman
tzaman

Reputation: 47780

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.

Upvotes: 1

Related Questions