Sorry for a perhaps newbie question, I had a hard time in the school.

Well, the title says the problem, let's look at example, which I stole from the coursera video-lectures about an algorithms:

Claim: if $T(n) = a_{k}n^{k}+...+a_{1}n+a_{0}$ then $T(n)=O(n_{k})$

It is a formula of one of a videos, you may see here that $T(n)$ used as usual, it is a declaration of a function $T(n)$, which takes one argument n. That's pretty clear.

As you probably know the so called Big-Oh $O()$ returns a speed of an algorithm(in a worst case, but for now this doesn't matter). I can understand for now that in the statement $T(n)=O(n_{k})$ the autor wanted to say: "speed of the function $T(n)$ is equal to $n^{k}$". But it is absolutely not what I see! I see this "A result of a function $T(n)$ is equal to speed of calculating $n^{k}$". Because Big Oh is a function that takes a function as an argument, and returns it's speed. So this formula should be written as $O(T(n) )=n^{k}$ (or we may neglect an argument, as we know that the T is a function of one argument, and then the formula going to look like $O(T)=n^{k}$).

It is pretty confusing. If in the begin of a lectures I could somehow guess what the author talking about, then some videos later I stuck; I have no time to understand all the calculations of the autor(mostly because I am not Englishman), then I am trying to look at a pictures, and all the mess just blows my mind!

  • $\begingroup$ You shouldn't look at that equal sign as an equality. See this. $\endgroup$ – Git Gud May 25 '14 at 10:40
  • $\begingroup$ As an aside, $O(T) = n^k$ is bad notation. $O(T(n)) = n^k$ is reasonable, since we're comparing the rates at which two real numbers vary. If $f(n) = n^k$, then $O(T) = f$ is reasonable since we're comparing the rates at which two functions vary. But $O(T) = n^k$ isn't very good. $\endgroup$ – user14972 May 25 '14 at 10:49

Big-O is commonly used for complexity analysis of algorithms, as you said, but it actually comes from mathematics, in the study of asymptotic growth.

For example, when I say in English "sorting $n$ integers can be done in $O(n\log n)$ time", it means more precisely the following:

Let $T(n)$ be the amount of time (either in seconds, or in amount of computer operations) it takes to sort $n$ integers. Then $T(n) = O(n \log n)$.

To understand the last part of the above we need to understand what big O means.

And this is the definition: A function or mathematical expression is said to be $O(\text{something})$, if there exists a positive constant $C$ such that the function or expression does not exceed $C$ times $\text{something}$.

In the above example, with sorting integers, this means:

There exists a constant $C>0$ such that it takes no more than $C\cdot n\cdot \log n$ seconds to sort $n$ integers.

And in the example in your question, it means:

Suppose $T(n) = a_k n^k + \ldots + a_1 n + a_0$. Then there exists a constant $C > 0$ such that $T(n) \le C n^k$.

  • $\begingroup$ Here's the problem anyway! Because $T(n) \le C n^k$ is yet means "result of $T(n) \le C n^k$, isn't it? $\endgroup$ – Hi-Angel May 25 '14 at 10:52
  • $\begingroup$ Yes, that's what it means. Note that $T(n)$ is not an algorithmic function, but a meta-algorithmic function - it calculates the amount of steps in some algorithm, it doesn't calculate the algorithm itself. We don't care how fast it takes a computer to calculate $T(n)$. We just care about the value. $\endgroup$ – Yoni Rozenshein May 25 '14 at 10:56
  • $\begingroup$ I just remember, you've redefined $T(n)$ as amount of time to execute an algorithm. But in my example it's a definition of a function, that executes the algorithm itself, not the time, isn't it? $\endgroup$ – Hi-Angel May 25 '14 at 11:01
  • $\begingroup$ In your example it's the definition of a mathematical function, and no algorithm is mentioned. (Presumably, it describes the amount of steps in some algorithm, but maybe not.) $\endgroup$ – Yoni Rozenshein May 25 '14 at 11:09
  • $\begingroup$ So the $a_{k}n^{k}+...+a_{1}n+a_{0}$ is not the algorithm? $\endgroup$ – Hi-Angel May 25 '14 at 11:12

Big-Oh does not inherently measure speed. It describes the overall growth of arbitrary functions as their argument(s) tends to infinity (or sometimes towards a different point). One of the main applications of Big-Oh is complexity theory, where the functions considered could be the running time of an algorithm as a function of its input, or the memory footprint of an algorithm as a function of its input. So when we say $f(n)=O(g(n))$ (which by the way is an abuse of the equals sign, but hey it's established), we only say that there exists a constant $c$ such that $|f(n)|<cg(n)$ for almost all $n\in\mathbb N$.

  • $\begingroup$ I don't think that in my example is shown a function, that is the time of an algorithm itself. It's a function, that executes the "$a_{k}n^{k}+...+a_{1}n+a_{0}$", isn't it? $\endgroup$ – Hi-Angel May 25 '14 at 11:19

Others already pointed to the definition of $O(x)$. I'll try to write it in a different perspective.

$O(x)$ is not a function. It's a set of functions represented by a single base function like $x$, $x^n$, $1/x$, etc. These functions within the same set are similar to how fast they grow such that they can be treated being almost the same in analysis of algorithms since we assume that algorithms will take in a extremely large numbers.

For example, $x^2$ and $2x^2$ increase just about the same rate such that for huge $x$, we can just discard that constant and say both functions are $O(x^2)$.

  • $\begingroup$ Anyway, in the example the equality sign compares the result of a function T(n) with it's time. Isn't this wrong? $\endgroup$ – Hi-Angel May 25 '14 at 11:45
  • $\begingroup$ In $O$ notation, the equality sign doesn't strictly mean $T(n)$ is exactly equal to $O(n^k)$ or $n^k$. Instead, it means $T(n)$ is within a set of functions that grows similar to $n^k$. If it makes it easier to understand, the equality sign can be more seen as a $\in$ symbol. Some examples, $3x = O(x)$, $10x^3 = O(x^3)$, $x^2 + x + 5 = O(x^2)$. $\endgroup$ – user64878 May 25 '14 at 12:24

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.