0
$\begingroup$

I have here a function (written in python), which computes the sum of all numbers from $a$ to $b$. I'd like to know how to find mathematically it's time complexity (without using the master theorem). How can one do that?

Here's what I've tried so far:

I managed to express the left recursive side as: $\frac{\left(2^{k}-1\right)a+b}{2^{k}}$ (after writing the mid as a sum like so $\frac{a+\frac{a+\frac{a+b}{2}}{2}}{2}$ (the fraction may go further for large $k$-s).

comparing the resulting formula to $a$ as a base case for the function to stop does not yield results: $$\frac{\left(2^{k}-1\right)a+b}{2^{k}}=a\Rightarrow-a+b=0\Rightarrow a=b$$ which brings me back to the "starting point" and gives no new information about $k$. I'd really appreciate your help :)

$\endgroup$

1 Answer 1

1
$\begingroup$

An easy approach is by noticing that the two recursive calls apply to two subintervals that partition the input interval. As the recursion stops on singletons, the function will exit immediately exactly n = b-a+1 times (the number of singletons in [a,b]).

But any call involves at most two subcalls, so that the total number of calls cannot exceed

n + n/2 + n/4 + n/8 + ... < 2n.

Clearly, that fuction takes time Θ(n).

$\endgroup$
5
  • $\begingroup$ Thank you, I have a few followups: why is the number of calls the sum of this? also, is there a more "equational" way to get this result? for example as in the proof for the time complexity of binary search here $\endgroup$
    – bendaMan
    Sep 9, 2020 at 15:20
  • $\begingroup$ @bendaMan: my answer is perfectly equational. "why is the number of calls the sum of this" is what my second paragraph tries to explain. $\endgroup$
    – user65203
    Sep 9, 2020 at 15:23
  • $\begingroup$ I see, but still why isn't my equation working? $\endgroup$
    – bendaMan
    Sep 9, 2020 at 15:28
  • $\begingroup$ @bendaMan: I don't think that your computation is finalized. $\endgroup$
    – user65203
    Sep 9, 2020 at 15:42
  • $\begingroup$ how should it be continued? $\endgroup$
    – bendaMan
    Sep 9, 2020 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.