108
Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$.
Note that this also clarifies some caveats of the $O$ notation.
For example, we write that $(1/2) n^2 + ...
77
The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no place in a textbook. Make no sudden movements. Put the book down. Step away from the book.
We say that the "order of growth" of the sequential search ...
48
Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$.
Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on..
Per se, the two have nothing to do with ...
44
$O$ is a function
$$\begin{align}
O : (\mathbb{N}\to \mathbb{R}) &\to \mathbf{P}(\mathbb{N}\to \mathbb{R})
\\ f &\mapsto O(f)
\end{align}$$
i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic bound of (at most) $f$. And strictly speaking the correct notation is thus
$$
(n \mapsto T(n)) \in O(n\mapsto f(n))
$$
...
26
Consider the following algorithm (or procedure, or piece of code, or whatever):
Contrive(n)
1. if n = 0 then do something Theta(n^3)
2. else if n is even then
3. flip a coin
4. if heads, do something Theta(n)
5. else if tails, do something Theta(n^2)
6. else if n is odd then
7. flip a coin
8. if heads, do something Theta(n^4)
9. else if ...
24
To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size.
For instance, we say that a function that takes $3n$ steps is $O(n)$, because, ...
22
It's a variant of the big-O that “ignores” logarithmic factors:
$$f(n) \in \tilde O(h(n))$$
is equivalent to:
$$ \exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right) $$
From Wikipedia:
Essentially, it is big-$O$ notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate ...
19
In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely not be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.
19
Wikipedia says:
An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.
$\mathcal{O}(\log n)$ is upper bounded by $\mathcal{O}(n)$, and $\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.
17
Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual:
$$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$
$$ \gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$
Here $\alpha(n)$ denotes the inverse Ackermann function.
16
There are many examples for such functions. Perhaps the easiest way to understand how to get such an example, is by manually constructing it.
Let's start with function over the natural numbers, as they can be continuously completed to the reals.
A good way to ensure that $f\neq O(g)$ and $g\neq O(f)$ is to alternate between their orders of magnitude. For ...
16
You need to ignore for a moment the strong feeling that the "$O$" is in the wrong place and plough on with the definition regardless. $f(n) = \log^{O(1)}n$ means that there exist constants $k$ and $n_0$ such that, for all $n\geq n_0$, $f(n) \leq \log^{k\cdot 1}n = \log^k n$.
Note that $\log^k n$ means $(\log n)^k$. Functions of the form $\log^{O(1)}n$ are ...
16
In order to compare 2 complexities just calculate a limit of their ratios as below:
$\displaystyle\begin{align*}
\lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}}
&= \lim_{n\to\infty}\frac{log(n)}{\sqrt{n}}
= \lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}}
= \lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\
&\underset{\left| k = \...
15
We first need to clarify what we mean by "does this hold if we have an infinite chain?".
We interpret it as an infinite sequence of functions $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ such that for all $i$ we have $f_i(n) = O(f_{i+1}(n))$. Such a sequence might not have a last function.
We can look at the limit of the functions in the sequence, i.e. $...
14
Tell the lecturer they're wrong. Take the function
$$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$
This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.
Here is a monotone example, which might be more convincing:
$$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$
14
Yes, of course. This is fine and perfectly acceptable. It is common and standard to see algorithms whose running time depends upon two parameters.
For instance, you will often see the running time of depth-first search expressed as $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. This is perfectly valid. The ...
13
First, let's unpack what $\Theta(1)$ means.
Big $O$, and big $\Theta$, are classes of functions. There's a formal definition here, but for the purposes of this question, we say that a function $f$ is in $O(1)$ if there's a constant $c$ where, for all $x$, $f(x) \leq C$. That is, $f$ grows at most as fast as a constant function.
Big-$\Theta$ doesn't mean ...
13
Formally speaking, $O(f(n))$ is a the set of functions $g$ such that $g(n)\leq k\,f(n)$ for some constant $k$ and all large enough $n$. Thus, the most pedantically accurate way of writing it would be $T(n)\in O(f(n))$. However, using $=$ instead of $\in$ is completely standard, and $T(n)=O(f(n))$ just means $T(n)\in O(f(n))$. This is essentially ...
12
With some algebra (and changing the constant in the $O(n)$), we can actually change the bases.
$$3^n = (2^{\log_2 3})^n = 2^{n\log_2 3}$$
Since $\log_2 3$ is a constant, $n\log_2 3 = O(n)$. So $3^n = 2^{O(n)}$.
I'm not sure what you mean by "$3^n$ grows faster than any exponential function with a base of 2." $2^n = o(3^n)$ of course but it seems you ...
12
One example is $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.
We have $g(n) = \sqrt{G(n)}$, so $g(n) = o(G(n))$.
Meanwhile, of course, $g(n+1) = G(n)$ so $g(n+1) = \Theta(G(n))$, so $g(n+1)\neq o(G(n))$
Why double exponential? When we add one to $n$, we want the effect to be more than a multiplicative constant (because big $O$ notation hides multiplicative, ...
12
To elucidate on the discussion in the comments, it matters what you're measuring growth relative to.
As mentioned by @Kaveh, $O(mn)$ is not linear in both at the same time, but is linear if one is a constant and the other one grows.
On the other hand, $O(m+n)$ would likely be considered linear. Intuitively, if $m$ doubles, or if $n$ doubles, or even if ...
12
Since $1+2+\dots+n =O(n^2)$, it is tempting to suggest that $O(1)+O(2)+\dots+O(n) = O(n^2)$ ... but this is not in fact valid. The reason is that there might a different constant for each term in the sum.
An example
Let me give an example. Consider the sums $S(1) = 1^2$, $S(2) = 1^2 + 2^2$, $S(3) = 1^2 + 2^2 + 3^2$, $S(4) = 1^2 + 2^2 + 3^2 + 4^2$, and so ...
12
The proof is by counterexample. Consider the following functions:
$$f_1(x) = 2x$$
$$f_2(x) = x+1$$
$$g_1(x) = x$$
$$g_2(x) = x$$
First, we can see that $f_1 = \Theta(f_2)$ and $g_1 = \Theta(g_2)$. Finding constants to prove the four big-Oh relationships involved is straightforward (in particular for $g_1$ and $g_2$).
Next, we can observe that $f_1 - g_1 = ...
12
Summary: $f$ and $g$ are typically functions, and $f$ is typically the runtime and $g$ is typically the asymptotic complexity of $f$. But if any of this is unclear from the description, I think it is best to either find another explanation, or to forget about application domains and intuitions for a second and go back to the definitions.
They're both ...
12
$O(n^2 \times \log(n))$ is greater than $O(n^2)$ but it is smaller than $O(n^{2 + \epsilon})$ for any $\epsilon > 0$, however small $\epsilon$ is (see here).
In particular, it is smaller than $O(n^{2.5})$. You're basically comparing the growth of $\log$ and square root.
11
The key thing to keep in mind here is that the equals sign in $f = O(g)$ does not behave as an equals sign usually would. The reason is that $O(g)$ is not actually a function but a set of functions. For example, you can think of $O(n^2)$ as being a set which, among many other functions, contains the functions $n$, $5 \sqrt n$, $\log^5 n$, etc. So as the ...
11
First, as other answers have already explained, $O(3n) = O(n)$, or to put it in words, a function is $O(3n)$ if and only if it is $O(n)$. $f = O(3n)$ means that there exists a point $N$ and a factor $C_3$ such that for all $n \ge N$, $f(n) \le C_3 \cdot 3n$. Now pick $C_1 = 3 C_3$: for all $n \ge N$, $f(n) \le C_1 \cdot n$, so $f = O(n)$. The proof of the ...
answered Feb 20 '13 at 17:46
Gilles 'SO- stop being evil'
39.8k7 gold badges105 silver badges170 bronze badges
11
That depends on context. In theoretical computer science, usually every polynomial time algorithm is considered 'efficient'. In approximation algorithms for example a runtime of $n^{1/\epsilon^{1/\epsilon}}$ would be considered efficient, even though it won't be usable in practice for any reasonable value of $\epsilon$. An algorithm for SAT that runs in $n^{...
11
"$O(1)$" is used because it is simple, clear and unambiguous. "$O(C)$" would be a poor choice of notation because in any given context, $C$ might have a specific meaning, such as the number of clauses in a CNF formula, the number of components in a graph.
11
Think in terms of the definition: $f(m)=O(g(m))$ means that there exists some constants $c>0, M\ge 0$ such that $f(m) \le c\cdot g(m)$ for all $m\ge M$ so when you write
$$
\sum_{i=1}^nO(1)
$$
you mean that there are $n$ functions, $f_1, f_2, \dotsc, f_n$ and constants $c_1, c_2, \dotsc, c_n$ such that $f_i(m)\le c_i\cdot1$ for all sufficiently large ...
Only top voted, non community-wiki answers of a minimum length are eligible
