# Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

So far we have learned Recursion Tree, Substitution Method, and Master's Theorem. I'm not sure how we can find lower AND upper bounds. I know that using Master's Theorem, we get $$T(n) = \Theta(n^4)$$, but how can I find both upper and loewr?

• If the master's theorem gives you a Theta class (I haven't checked), it already is a tight upper and lower bound asymptomatically. I am not sure what you're asking here? Sep 25, 2019 at 20:48
• I was wondering when the question said give upper and lower bound, I thought it was asking for the Big Omega and Big O Sep 26, 2019 at 0:01
• I saw a solution of this problem being $T(n)= cn + (\frac{8}{7}) +n^4$, but I have no idea how to get there . Sep 26, 2019 at 0:03
• @donnyan Doing the maths in my had, I came up with about (8/7)n^4. It's easy and a method that you should always use: Calculate T(2^10) = 2T(2^9) + 2^40 = 2(2T(2^8) + 2^36) + 2^40 = 4T(2^8) + 2^37 + 2^40 etc. It gives you an immediate idea what's going on. Or calculate T(1), T(2), T(4), T(8), T(16)... until you find a system. Sep 26, 2019 at 6:59
• Well, a lower bound is $1$ and an upper bound is $n!^{n!}$. In other words, you have to be more precise with what you want to know.
– orlp
Sep 26, 2019 at 7:41

It seems that you have overlooked the fact that $$f(n) \in \Theta(n^4)$$ already implies both an upper bound of $$f(n)\in O(n^4)$$ and a lower bound of $$f(n)\in \Omega(n^4)$$. Intuitively, $$\Theta$$- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".
It automatically implies that $$O(n^4)$$ and $$\Omega (n^4)$$ because of $$f(n)\in O(n^4)$$ and master theorem $$\Theta (n^4)$$.