CODEWITHSUNDEEP
algorithmtime-complexityrecurrence
Sake
Sake

Reputation: 96

How can I solve this recurrence relation

I have a recurrence relation: enter image description here

I transformed it into enter image description here

How can I prove T(n) is belong to BigOmega(2^n)

Upvotes: 2

Views: 45

Answers (1)

Berthur
Berthur

Reputation: 4495

So let's look at T(n) = 2 * T(n - 1) + T(n/2) + 1/2.

Let us compare this to the recurrence relation where the smaller terms are stripped:

S(n) = 2 * T(n - 1)

We can obviously see that

T(n) = Ω(S(n))

so it only remains to show that S(n) = Ω(2n).

Let us expand S(n):

S(n) = 2 * T(n - 1)

= 2 * 2 * T(n - 2)

= 2 * 2 * 2 * T(n - 3)

We notice that we obtain 2 * 2 * ... * 2 = 2n.

Therefore, S(n) = Ω(2n) and thus T(n) = Ω(S(n)) = Ω(2n). □

Upvotes: 2

Related Questions