Using Substitution to Prove an Big O/upper bound is O(n^3)
I need to use a substitution method to prove and show that T(n) is in O(n³) for
$T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + 5n^3 $
for n ≥ 2, T(1) = 20
I am supposed to come up with an explicit guess for the upper bound instead of trying to reason using order notation.
thanks!
Answer
Answers can only be viewed under the following conditions:
- The questioner was satisfied with and accepted the answer, or
- The answer was evaluated as being 100% correct by the judge.
1 Attachment

4.8K
-
It took me about 35 minutes to write this solution. You should offer higher amounts in future, otherwise your questions may not get answered.
The answer is accepted.
Join Matchmaticians Affiliate Marketing
Program to earn up to a 50% commission on every question that your affiliated users ask or answer.
- answered
- 999 views
- $5.00
Related Questions
- Compute $\lim_{x \rightarrow 0} \frac{1-\arctan (\sin(x)+1)}{e^{x}-1}$
- Find $\lim _{x \rightarrow 0^{+}} \sqrt{x}\ln x$
- Compute $\lim_{n \rightarrow \infty} \ln \frac{n!}{n^n}$
- Constructing Monotonic Sequences Converging to an Accumulation Point in a Subset of $\mathbb{R}$
- [Year 12 Trigonometric Functions] Research assignment investigation, using tidal waves to model data.
- Inequalities + limits questions
- limit and discontinous
- Proof of P = Fv.