# How to bound a running time equation? [duplicate]

I simply need a standard way to find the upper and lower bound of a running time equation (please no shortcuts that only work for this specific problem)....

Example: $T(n)=\frac{c}{5}(4^{\left \lfloor \log_{4} (2n^{2}) \right \rfloor +1}-1)$

I think I understand how to put it in $\Theta$, $\Omega$, and $O$ after I get the bounds.... But I can't figure out a standard way to find the bounds for the running time of an algorithm (it's all unrelated or obscure shortcuts) for any given formula. Any help out there?

EDIT: Apparently it might be thought I am asking for a specific number for each bound. I am not, I'm looking for how to find the equation that the bound gives.... For instance, on a problem (not this one), a bound might be $3^\frac{\ln a}{\ln n}+1$ for a certain bound.... The actual problem says to show your work putting the equation into $\Theta$ by bounding it on the upper and lower bounds. I need to know how to show work for that on this and similar problems. Make more sense?

## marked as duplicate by David Richerby, Raphael♦Jul 21 '14 at 0:07

• There is no unique upper or lower bound: there are infinitely many of each. As written, your question seems rather broad and the only answer is the unhelpful one: find a fairly simple expression that's bigger/smaller than your $T(n)$ for large enough $n$. – David Richerby Jul 20 '14 at 22:28
• I'm sorry if the question looks like it's asking for a specific number for upper\lower bounds.... I'm actually asking how to find the upper\lower bound equations. For example, an upper bound might be $3^\frac{\ln a}{\ln n}+1$ of a particular equation. I just basically am asking how to be able to show my work on this type of problem.... – user20275 Jul 20 '14 at 22:40
• You keep saying the upper/lower bound. Upper and lower bounds are not unique. For example, $0$, $\log n$, $n$ and $n\log n$ are all lower bounds for the formula $T(n)$ in your question. – David Richerby Jul 20 '14 at 22:46
• @TGxPatriot Use the definition of big $\Theta$. Find explicit $\alpha,\beta$ such that $\alpha n^2 \leq T(n) \leq \beta n^2$ for large enough $n$. – Yuval Filmus Jul 20 '14 at 22:52
Every function is big $\Theta,\Omega,O$ of itself, so you can already put your result in big $\Theta,\Omega,O$ notation. Using $4^{\log_4 (2n^2)} = 2n^2 = \Theta(n^2)$, you can also write $T(n) = \Theta(n^2)$; I'll leave you the details.
• @TGxPatriot I can't follow your question. It's like asking how does one solve equations. There is no recipe. That said, in most cases deriving succinct asymptotic bounds is not difficult, and you mostly have to use relations like $f + g = \Theta(f)$ if $g = o(f)$. – Yuval Filmus Jul 20 '14 at 22:51