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 be viewed only if
- The questioner was satisfied and accepted the answer, or
- The answer was disputed, but the judge evaluated it as 100% correct.
1 Attachment

4.4K
-
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 50% commission on every question your affiliated users ask or answer.
- answered
- 385 views
- $5.00
Related Questions
- Find the composition function $fog(x)$
- Calculus Questions - Domains; Limits; Derivatives; Integrals
- Calculus - functions, method of Least Squares
- Prove that $\lim_{\epsilon \rightarrow 0} \int_{\partial B(x,\epsilon)} \frac{\partial \Phi}{\partial \nu}(y)f(x-y)dy=f(x)$
- Find $lim_{x \rightarrow 0^+} x^{\ln x}$
- Inclusion-Exclusion and Generating Function with Coefficient (and Integer Equation)
- Find $\lim_{x\rightarrow \infty} \frac{1}{x^2}\sin x^2\tan x$
- Can someone translate $s_j : \Omega \hspace{3pt} x \hspace{3pt} [0,T_{Final}] \rightarrow S_j \subset R$ into simple English for me?