CODEWITHSUNDEEP
algorithmtime-complexityasymptotic-complexityrecurrencemaster-theorem
tzegian
tzegian

Reputation: 589

algorithm find O(n) with two T(n) on the other side of the recurrence equation

next days I will have my exam on algorithms, the professor asked us to learn how to find O(n) of equations at this form:

T(n) = T(n/3) + T(n/4) + 5n

T(n) = T(n/3) + 2T(n/4) + 5n

T(n) = T(n/3) + T(n/4) + 15n

T(n) = 2T(n/3) + T(n/4) + 4n

I know how to use master theorem but I doubt I can use it somehow here. My professor also hasn't showed us even one example on how to solve this, on google I couldn't find much (or didn't know how to find a solution - how to search for it) so is it possible someone show me how to solve the aboves step by step?

Thanks in advance.

PS: Sorry about the probably wrong title, as I said, I don't know how exactly to present what I want.

Upvotes: 1

Views: 337

Answers (1)

OmG
OmG

Reputation: 18838

As mentioned in the comment, because T(n/3) > T(n/4) you can find an upper bound for each of the above equations (this condition is true for increasing T(n)).

T(n) = T(n/3) + T(n/4) + 5n => T(n) < 2T(n/3) + 5n =>(using master theorem) T(n) = O(n) Also, we can say T(n) = \Theta(n) as because of 5n we can say T(n) = \Omega(n).

T(n) = T(n/3) + 2T(n/4) + 5n => T(n) < 3T(n/3) + 5n =>(using master theorem) T(n) = O(nlog(n))

T(n) = T(n/3) + T(n/4) + 15n => T(n) < 2T(n/3) + 15n =>(using master theorem) T(n) = O(n)

T(n) = 2T(n/3) + T(n/4) + 4n => T(n) < 3T(n/3) + 4n =>(using master theorem) T(n) = O(nlog(n))

Upvotes: 3

Related Questions