asymptotic complexity based off running time?

Question

How do you go about finding the asymptotic complexity based off a running time? For example:

If the run time of a recursive algorithm is given as

T(n) = 2 T(n/2) + O(n)

considering the Master Theorem, what is its asymptotic complexity?

Could someone explain the steps on how to figure this out?

Answer 1

For the Master Theorem, there are 3 different cases to solve.

First step is to understand which case applies.

For questions involving Master Theorem, our general formula is T(n) = aT(n/b) + f(n)

So first thing to do is compare n^(logb a) with f(n).

Simply whichever is bigger that's the complexity of it(these are Cases 1 and 3) and if they are equal then you multiply the result with lgn, such as if you have a case like T(n) = 16 T(n/4) + O(n^2) then n^(logb a) would make n^2 as well as f(n) = n^2 so the answer would be Θ(n^(2)*lgn), which is by using the case #2 of the Master Theorem.