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
You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement.
$f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the ...
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 ...
49
If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions.
If $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then
$c=0 \qquad \ \,\iff f \in o(g)$,
$c \in (0,\infty) \iff f \in \Theta(g)$ and
$c=\infty \quad \ \ \ \iff f \in \omega(g)$.
With this, you should be able to order most of the ...
43
Big O: upper bound
“Big O” ($O$) is by far the most common one. When you analyse the complexity of an algorithm, most of the time, what matters is to have some upper bound on
how fast the run time¹ grows when the size of the input grows. Basically we want to know that running the algorithm isn't going to take “too long”. We can't express this in actual time ...
answered Mar 8 '12 at 3:14
Gilles 'SO- stop being evil'
37.8k7 gold badges101 silver badges166 bronze badges
43
$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))
$$
...
40
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 ...
33
You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables.
Simply speaking, since
$$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$
you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent ...
25
Believe it or not, it seems (in my experience) that many algorithms people have actually not thought about what the big O notation formally means, and when asked about it, you can get several different answers. Some issues are discussed in the paper On Asymptotic Notation with Multiple Variables by Rodney R. Howell.
Curiously, it also seems that most ...
22
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, ...
20
Another tip: sometimes applying a monotone function (like log or exp) to the functions makes things clearer.
18
Typically $O$ is used for stating upper-bounds (an estimate from above), while $\Omega$ is used to state lower-bounds (an estimate from below), and $\Theta$ is used when they match, in which case you can use $\Theta$ in place of them (usually) to state the result.
18
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.
18
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 ...
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.
17
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
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 ...
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
Recall that for $k > 1$, by definition we have $\log^*k = \log^*(\log{k}) + 1$.
By applying the definition twice, we see that $\log^*(2^{2^n}) = \log^*n + 2$. Now we can compare $\log^*n + 2$ and $(\log^*n)^2$.
15
It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.
This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. ...
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
Do what you did, but let $a = (3^{0.2})$... that should do it, right?
The reason that what you did didn't work is as follows. The big-oh bound is not tight; while the logarithm to the fifth is indeed big-oh of linear functions, it is also big oh of the fifth root function. You need this stronger result (which you can also get from the theorem) to do what ...
14
Let me start of with a recommendation: treat Landau notation just as you (should) treat rounding: round rarely, round late. If you know something more precise than $O(.)$, use it until you are done with all calculations, and Landauify at the end.
As for the question, let's dig through this abuse of notation¹. How would we interpret something like $h \in O(f ...
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
Yes. Because they differ only by a constant factor. Remember high school math:
$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$.
13
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. $$
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
