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 + ...
78
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 ...
53
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))
$$
...
27
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 ...
26
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
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$.
19
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 ...
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 = \...
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
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
"$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 ...
11
Let's start with the simple case $g = 1$, and $f$ having positive values only (that's all we care about with functions that represent complexity).
$f \in O(1)$ means that $f$ is bounded: there exists $B$ such that $f(n) \le B$ (for sufficiently large values of $n$).
$f \in o(1)$ means that $\lim_{n\to\infty} f(n) = 0$.
$f \in \Theta(1)$ means that $f$ is ...
answered May 15 '16 at 15:22
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
11
First, let me mention that judging from the final result, in this context $O(f(N))$ means a function $g(N)$ such that $|g(N)| \leq Cf(N)$ for some $C>0$ and all $N$.
The first step is simple: we divide both numerator and denominator by $2a_0 N$. This gives us
$$
\frac{2\ln(2N) + O(2N)/2a_0N}{\ln N + O(N)/2a_0N}.
$$
Now if $f(N) = O(N)$ then $f(N)/2a_0N = ...
11
Prologue: The big $O$ notation is a classic example of the power and ambiguity of some notations as part of language loved by human mind. No matter how much confusion it have caused, it remains the choice of notation to convey the ideas that we can easily identify and agree to efficiently.
I totally understand what big $O$ notation means. My issue is when ...
10
Basically, without further information you know nothing about the asymptotic growth of $f \cdot g$.
Let's unfold the definitions:
$\qquad f \in \Omega(n) \implies f(n) \leq cn$ and
$\qquad g \in O(n) \implies g(n) \geq dn$
for some $c,d \in \mathbb{N}$ and $n$ greater than some constant.
Now it's clear that you get no bound on $g \cdot f$; you have ...
10
The counterexample is fine. Any function that is $O(n)$ is also $O(n^2)$ – if a function's "smaller than" $n$, it's also "smaller than" $n^2$.
And note that even weaker statements are false. In fact, there is no function $g$ such that $T_1,T_2=O(f)$ implies that $T_1(n)/T_2(n)=O(g(n))$. For example, take $T_1(n)=1$ and $T_2(n)=1/g(n)^2$. ...
10
In The Algorithm Design Manual [1], you can find a paragraph about this issue:
The Big Oh notation [including $O$, $\Omega$ and $\Theta$] provides for a rough notion of equality when comparing
functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its
meaning can always be resolved by going back to the definitions in terms of ...
9
Part 1
I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've been taught, and what other misconceptions float around this topic. I wrote this in the form of an imaginary discussion.
The following discussion is based on ...
9
There is no reason why you can't write $O(2)$ instead. $O(1)$ can equally be expressed as $O(2)$, or $O(1/2)$ or $O(2\pi)$, etc. (Untitled explained why it can't be $O(0)$.) It's purely a matter of convention.
9
The term "polynomial delay", in this case, appears to refer to the time complexity of generating (or enumerating) subsequent solutions. This is a bit different than our standard notion of runtime, since we usually only consider single executions of a machine or algorithm on an input. The delay complexity measure deals with time spent between enumerations ...
9
Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the functions themselves. It's not wrong per se to say that $7x^2 + 4x + 2 = \Theta(7x^2)$, but it's not informative because $7x^2 + 4x + 2 = \Theta(3x^2)$ is also true ...
9
Big-$O$ and $\Omega$ are actually defined entirely separately from complexity theory. All they are is properties of functions.
$O$ is used for asymptotic upper-bounds of a function, and $\Omega$ is used for asymptotic lower bounds. If for some functions $f,g$ we have $f \in O(g)$, and $f \in \Omega(G)$, you can use big-theta notation, $f \in \Theta(G)$.
So,...
9
This is an abuse of notation that can be made sense of by the generally accepted placeholder convention: whenever you find a Landau term $O(f)$, replace it (in your mind, or on the paper) by an arbitrary function $g \in O(f)$.
So if you find
$\qquad f(n) = \log^{O(1)} n$
you are to read
$\qquad f(n) = \log^{g(n)} n$ for some $g \in O(1). \hspace{5cm} (1)$...
Only top voted, non community-wiki answers of a minimum length are eligible