Geek Answers Handbook

The time complexity of the relation T (n) = T (n-1) + T (n / 2) + n

for relationship

T (n) = T (n-1) + T (n / 2) + n

can I first solve the term (T (n-1) + n) that gives O (n ^ 2), then solve the term T (n / 2) + O (n ^ 2)?

according to the main theorem, which also gives O (n ^ 2), or is it false?

+7
algorithm complexity-theory time-complexity recurrence master-theorem
source share
2 answers

No, you cannot solve this using Mater’s theorem.

You need to solve it using the Akra-Bazzi method , a cleaner generalization of the famous master theorem.

  • The master theorem assumes that the subtasks are the same size.

  • The main theorem concerns recurrence relations of the form

T (n) = a T (n / b) + f (n), where a> = 1, b> 1.

I do not find steps here to decide for you to work on it. If you have additional problems resolving this issue, please comment on this below. Good luck ...

+1
source share

I do not think that your approach is generally correct. When you drop the term T (n / 2) to calculate the complexity of the term T (n-1), you end up underestimating the size of the term T (n-1).

For a specific counterexample:

T(n) = T(n-1) + T(n-2) + 1

Your technique will also come up with T (n) = O (n ^ 2) for this, but the real complexity is exponential.

+2
source share

More articles:


All Articles