1
$\begingroup$

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?

$\endgroup$
8
  • 1
    $\begingroup$ $O$ and so on give relationships between mathematical functions. It doesn't matter where those functions came from or what they're being used to measure. You have the function $5n^3+100n^2+32n$ so you should be able to tell from the definitions whether that function is $O(n^3)$, $\Theta(n^2)$ and/or $\Omega(n)$. $\endgroup$ Aug 14, 2015 at 14:46
  • $\begingroup$ Oh and according to my book, T(n) means the time taken for an algorithm to run with n elements. $\endgroup$
    – zkirkland
    Aug 14, 2015 at 14:51
  • 2
    $\begingroup$ No, $T$ is just some function, which needs to be defined. $T$ may well be used to measure the running time of some function but, unless you actually say that, it's just a function. (In the same way that saying "Consider a car of mass $m$" means that in this case, we're thinking about a car with mass $m$, but doesn't mean that $m$ always stands for the mass of cars.) $\endgroup$ Aug 14, 2015 at 14:56
  • $\begingroup$ I guess I did not understand what you meant when you asked me what T is. And my previous answer could be taken to mean "My book defines T(n) as the time it takes to run this algorithm with 'n' elements." Anyway this is inconsequential. I still do not have an answer to my question. $\endgroup$
    – zkirkland
    Aug 14, 2015 at 15:05
  • $\begingroup$ An algorithm (or its analysis) cannot be $5n^3 + 100n^2 + 32n$ any more than it can be blue or be Christian. $\endgroup$ Aug 14, 2015 at 15:06

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Ok, so when I analyze the algorithm, if I want worst case, I analyze it as worst case. If I want average-case running time, I analyze the algorithm as average-case...etc. So my equation above could be any one of the notations (big-oh, theta, or omega) depending on how I analyzed the algorithm to begin with. Is this correct? $\endgroup$
    – zkirkland
    Aug 14, 2015 at 15:22
  • $\begingroup$ No. If for you $T(n)$ is always the worst case running time, then that's how you must analyze your algorithm. $\endgroup$ Aug 14, 2015 at 15:25
  • $\begingroup$ Why is that? Why will it never be anything else? What do you mean when you say "for you"? $\endgroup$
    – zkirkland
    Aug 14, 2015 at 15:29
6
$\begingroup$

The key point is that $O(\cdot)$ and friends describe relationships between functions. Functions are purely mathematical objects and it doesn't matter what they're being used to measure. This is similar to the way that $<$ and friends describe relationships between numbers and it doesn't matter what those numbers are being used to measure.

So, in particular, it doesn't matter if your function is being used to measure the running time of some algorithm. It doesn't even matter if your function is being used to give, say, an upper bound on the running time of an algorithm. If I want to, I can give you an upper bound on a function that's a lower bound for the running time. It's not very useful to do that but, because $O(-)$ doesn't care what the function is measuring, it makes perfect mathematical sense. This is a bit like saying, "Jane is less than 1.75m tall and John is taller than her": I've given you an upper bound for Jane's height and Jane's height is, in turn, being used as a lower bound for John's. OK, John could have any height at all, but the mathematics makes sense.

So, all $T(n)=O(f(n))$ says is that the function $g$ is an upper bound for the function $T$, up to constant factors, for large enough inputs. It says nothing at all about any connection between the function $T$ and the real world: it doesn't say that $T$ is an upper bound for this or a lower bound for that.

With all of that out of the way, we can address the technical part of the question, but that really does just follow from the definitions, as I stated in comments.

Tou have a function $5n^3 + 100n^2 + 32n$ and you want to compare it to some other functions: $n$, $n^2$ and $n^3$. Let's call that function $T(n)$. Apparently, the function $T$ is somehow related to the running time of some algorithm but that doesn't matter for what's about to happen.

  1. $T(n) = O(n^3)$ because, for $n>100$, $T(n) \leq 5n^3 + n\cdot n^2 + n^2\cdot n = 7n^3$.

  2. $T(n)\neq O(n^2)$ because, for any constant $c$, and any $n\geq c$, $5n^3 + 100n^2 + 32n > 5n^3 \geq 5cn^2 > cn^2$. Similarly, $T(n)\neq O(n)$.

  3. $T(n) = \Omega(n^3)$ since, for any $n>0$, $T(n)> n^3$. Similarly, $T(n) = \Omega(n^2)$ and $T(n) = \Omega(n)$.

  4. $T(n) = \Theta(n^3)$ because $T(n) = O(n^3)$ and $T(n) = \Omega(n^3)$. $T(n)\neq \Theta(n^2)$ because $T(n)\neq O(n^2)$ and $T(n)\neq \Theta(n)$ because $T(n)\neq O(n)$.

$\endgroup$
1
  • $\begingroup$ Of course, let's not forget that T(n) is also in O(n^4), O(n^5), … $\endgroup$ Aug 14, 2015 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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