Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Tag Info

Accepted

### Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

The problem in the question is a good example for two related principles. Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to ...
• 33.2k
Accepted

### How to find parameter sets for a big-O expression to be fixed-parameter tractable?

Here is a simple method to find the parameters with respect to which (the problem whose worst runtime is bounded by) a big $O$-expression becomes fixed-parameters tractable (FPT), i.e., bounded by a ...
• 33.2k