2
$\begingroup$

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?

$\endgroup$
  • 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$ – Daniel Sep 25 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$ – donnyan Sep 26 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$ – donnyan Sep 26 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$ – gnasher729 Sep 26 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$ – orlp Sep 26 at 7:41
2
$\begingroup$

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".

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.