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?
5
-
6$\begingroup$ 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? $\endgroup$– DanielSep 25, 2019 at 20:48
-
$\begingroup$ I was wondering when the question said give upper and lower bound, I thought it was asking for the Big Omega and Big O $\endgroup$– donnyanSep 26, 2019 at 0:01
-
$\begingroup$ 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 . $\endgroup$– donnyanSep 26, 2019 at 0:03
-
$\begingroup$ @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. $\endgroup$– gnasher729Sep 26, 2019 at 6:59
-
$\begingroup$ 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. $\endgroup$– orlpSep 26, 2019 at 7:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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".
$\begingroup$
$\endgroup$
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)$.
