Determining BigO of a recurrence

Question

T (1) = c    
T (n) = T (n/2) + dn

How would I determine BigO of this quickly?

Answer 1

Use repeated backsubstitution and find the pattern. An example here.

Answer 2

I'm not entirely sure what dn is, but assuming you mean a constant multiplied by n:

According to Wolfram Alpha, the recurrence equation solution for:

f(n) = f(n / 2) + cn

is:

f(n) = 2c(n - 1) + c1

which would make this O(n).

Answer 3

Well, the recurrence part of the relationship is the T(n/2) part, which is in effect halving the value of n each time.

Thus you will need approx. (log2 n) steps to get to the termination condition, hence the overall cost of the algorithm is O(log2 n). You can ignore the dn part as is it a constant-time operation for each step.

Note that as stated, the problem won't necessarily terminate since halving an arbitrary value of n repeatedly is unlikely to exactly hit 1. I suspect that the T(n/2) part should actually read T(floor (n / 2)) or something like that in order to ensure that this terminates.

Answer 4

use master's theorem see http://en.wikipedia.org/wiki/Master_theorem

By the way, the asymptotic behaviour of your recurrence is O(n) assuming d is positive and sufficiently smaller than n (size of problem)