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 ...
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))
$$
...
43
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 ...
35
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 ...
27
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 ...
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 ...
20
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 ...
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.
18
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
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)$. ...
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
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
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
Yes. Because they differ only by a constant factor. Remember high school math:
$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$.
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
Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) \in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) \leq c\frac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, ...
12
Well, since this upper bound is not nearly tight, you can just use basic transformations to get
$$(n+1)!< (n+1)^{n}=2^{\log (n+1)^{n}}= 2^{n\log (n+1)}=O(2^{n\log n})\subset O(2^{(2^n)}). $$
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
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
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
"$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.
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
