CODEWITHSUNDEEP
algorithmfunctionbig-odiscrete-mathematics
Snowman
Snowman

Reputation: 32081

Determining BigO of a recurrence

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

How would I determine BigO of this quickly?

Upvotes: 2

Views: 758

Answers (4)

msft_coder
msft_coder

Reputation: 1

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)

Upvotes: 0

Ani
Ani

Reputation: 113472

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).

Upvotes: 2

mikera
mikera

Reputation: 106401

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.

Upvotes: 1

Dr. Snoopy
Dr. Snoopy

Reputation: 56417

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

Upvotes: 2

Related Questions