[Solved]: Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?

Problem Detail: 

If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = \Theta(n^2)$, and $T(n) = \Omega(n)$, and all of those be correct for that analysis?

I have read the formal definitions for all of these and it does not help me to understand them.

I understand that Big-Oh is an upper bound but how do you know if the algorithm you analyze is an upper bound? I mean, if I analyze an algorithm and I come up with $5n^3 + 100n^2 + 32n$, how do I know to make this Big-Oh?

Asked By : zachboy82

Answered By : Yuval Filmus

When we write that an algorithm satisfies $T(n) = O(n^3)$ (and this is not standard notation!), we mean that the running time of the algorithm, denote $T(n)$, satisfies $T(n) = O(n^3)$; here $n$ is some complexity measure of the input (in your case, the number of elements in the input). In fact, the function $T(n)$ is usually not the running time of the algorithm on inputs of length $n$, simply because the running time often depends on the input. Rather, usually it is taken as the worst-case running time of the algorithm on inputs of length $n$.

In your case, you are given something about the algorithm: the polynomial $5n^3+100n^2+32n$. You didn't say what the significance of this function is, but presumable it is the value of $T(n)$, that is, the worst-case running time of the algorithm on inputs of length $n$. In symbols, $$ T(n) = 5n^3 + 100n^2 + 32n. $$ (This guess is based on your question. It conceivably could have been an average-case running time or a space complexity.) In this case, you can say that $T(n) = \Theta(n^3)$, and in particular $T(n) = O(n^3)$ and $T(n) = \Omega(n^3)$. This follows from the definitions of these various terms ($\Theta,O,\Omega$).

In practice, you almost never analyze algorithms quite in this way:

1. Usually you only give an upper bound on the running time of the algorithm on any input of length $n$. This gives, in particular, an upper bound on $T(n)$, but doesn't give an upper bound on the average-case or best-case running time of the algorithm.

2. Usually your analysis doesn't result in an exact quantity, only in an upper bound. This is because the computation models are too complicated to analyze exactly. Exact analyses happen only when you're focusing on a different measure of time complexity, such as the number of comparisons in a sorting algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45256