Time complexity of a simple Python function

Question

I have been given a simply Python programme as such:

def boo(n):
    if n == 1:
        return 1
    else:
        return boo(n/2) + boo(n/2)

To boo, I have to find out the time complexity of the function. My idea is that since each n makes a call to two more boo's, the time complexity is O(2^n). However, it has been revealed that this is wrong. The answer has been revealed to me that the actual time complexity is O(n) without rationale given. My hunch is that boo(n/2) + boo(n/2) can be treated as 2*boo(n/2), but I am highly suspicious of this as I have seen similar scenarios before, and I vaguely remember that boo(n/2) + boo(n/2) cannot be equated to 2*boo(n/2) in terms of processing steps.

What would be a more appropriate way to understand this? I am still struggling with the ideas in order of growth (space and time complexity), so if anyone has any general advice or material that can possibly help me, I greatly welcome them. Thank you very much!

This may be naive, but it seems to me like boo(2048) calls boo(1024) twice, so doubling the input number doubles the number of operations. Which would make it O(n). Leaving aside the issue of using / instead of //. — khelwood
– khelwood, Commented Sep 25, 2020 at 14:50
@khelwood: Not naive, that's how it works. In raw calls, it always does n * 2 - 1 total calls, which is O(n) overall. — ShadowRanger
– ShadowRanger, Commented Sep 25, 2020 at 14:53
boo(n/2) + boo(n/2) does boo(n/2) twice, while 2*boo(n/2) does it only once, so clearly they can't be equally complex (unless that complexity is constant, but then it would be independent of n, so...). — molbdnilo
– molbdnilo, Commented Sep 25, 2020 at 15:00

ShadowRanger · Accepted Answer · 2020-09-25 14:54:26Z

3

This code is O(∞), as a non-power-of-two input will never complete (it will go from > 1 to < 1 without ever being == 1).

For powers of 2 (or if properly rewritten to do boo(n // 2) and not recurse infinitely), it's O(n), as each step halves the input, but then does that halved work twice, leading to overall linear performance (to be precise, boo is called 2n - 1 times for n being a power of 2). Changing the final line to return boo(n // 2) * 2 would get it to O(log n) performance.

edited Sep 25, 2020 at 14:54

answered Sep 25, 2020 at 14:50

ShadowRanger

158k12 gold badges221 silver badges314 bronze badges

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

4 Comments

Barmar Over a year ago

I wonder if this was originally written for Python 2.x, which does integer arithmetic and will always reach 1.

ShadowRanger Over a year ago

@Barmar: That seems likely. It could be written with // in Python 2 as well though (// works long before it was required to achieve floor division) to make it portable. Either way, when it works as expected, the code is clearly O(n).

a9302c Over a year ago

Understood now! I suppose the code was written too simplistically. But now assuming that n is a power of 2, is it fair to say that, first, the time complexity of 2*boo(n/2) is O(logn) because we are "dividing and conquering" by a factor of 2. But in the case of boo(n/2) + boo(n/2), the operation is performed in 2 "branches", hence it becomes O(n). Is this a fair evaluation?

ShadowRanger Over a year ago

@a9302c: You got it. It's splitting the work in half, then doing that halved work twice, so it's just "doing the original work" in a funny way. If you like to think of it this way, it's doing O(2 ** log₂n) work (the log₂n from the halving, the 2** from the doubling), which of course is equivalent to O(n).

Collectives™ on Stack Overflow

Time complexity of a simple Python function

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related