108
votes
Accepted
O(·) is not a function, so how can a function be equal to it?
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 ...
- 3,162
78
votes
Accepted
Order of growth definition from Reynolds & Tymann
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 ...
- 80.1k
54
votes
Accepted
How do O and Ω relate to worst and best case?
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 ...
- 70.8k
44
votes
O(·) is not a function, so how can a function be equal to it?
$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 ...
- 1,641
29
votes
Accepted
What does tilde mean, in big-O notation?
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:
...
- 1,917
28
votes
How do O and Ω relate to worst and best case?
Consider the following algorithm (or procedure, or piece of code, or whatever):
...
- 12.6k
21
votes
Accepted
Is log(n) in complexity class P?
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 ...
- 326
19
votes
Accepted
Can a Big-Oh time complexity contain more than one variable?
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 ...
D.W.♦
- 140k
16
votes
Accepted
What does $\log^{O(1)}n$ mean?
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 $...
- 80.1k
16
votes
Is O((n^2)*log(n)) greater than O(n^(2.5))?
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(...
- 261
13
votes
What does Θ(1) memory mean?
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 ...
- 29.1k
13
votes
O(·) is not a function, so how can a function be equal to it?
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 ...
- 80.1k
12
votes
Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?
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 ...
D.W.♦
- 140k
12
votes
Why do Θ-bounds not survive taking differences?
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)$. ...
- 12.6k
12
votes
Accepted
What do f(x) and g(x) represent in Big O notation?
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 ...
- 667
12
votes
Is O((n^2)*log(n)) greater than O(n^(2.5))?
$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^...
- 221
11
votes
Is $n$ times $O(1)$ equivalent to $O(n)$?
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 ...
- 14.5k
11
votes
Accepted
Big-O and not little-o implies theta?
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 ...
11
votes
Accepted
How did they cancel out O-terms in this fraction?
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 ...
- 268k
11
votes
O(·) is not a function, so how can a function be equal to it?
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 ...
- 33k
10
votes
What is the meaning of $O(m+n)$?
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 ...
- 341
10
votes
Counterexample to big-O claim looks wrong
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 ...
- 80.1k
10
votes
O(·) is not a function, so how can a function be equal to it?
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
...
- 3,394
9
votes
What does Big O notation actually specify?
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 ...
- 29.1k
9
votes
What does $\log^{O(1)}n$ mean?
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 ...
- 70.8k
9
votes
Why does the square root of n! grow exponentially faster than exponential functions?
$\log(n!)=\Theta(n\log n)$, (see Stirling's approximation), hence
$\frac{2^{O(n)}}{\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\log\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\Theta(n\log n)}=2^{-\left(\...
- 13.1k
9
votes
Accepted
Why does the square root of n! grow exponentially faster than exponential functions?
Throwing away gutter, this is the claim:
$\qquad\frac{c^n}{\sqrt{(n/2)!}} \to 0$ with at least exponential rate as $n \to \infty$.
That is, the sqare root of $(n/2)!$ grow (at least) exponentially ...
- 70.8k
9
votes
Big-O and not little-o implies theta?
No, it isn't true. Just consider $f(n) = n \bmod 2$ and $g(n) = 1$.
We have $\forall n ~ f(n) \leq 1 \cdot g(n)$, so $f(n) \in O(g(n))$.
$\lim_{n \to \infty} f(n)/g(n)$ is undefined and therefore ...
- 3,107
9
votes
Accepted
What does the "big O complexity" of a function mean?
First of all, when people talk about big O complexity, they refer to the complexity of an algorithm, usually its running time. A somewhat better term is big O asymptotics. Big O makes sense to ...
- 268k
8
votes
What is the meaning of $O(m+n)$?
Part 2
$$
\newcommand{\TR}{\mathbb{R}}
\newcommand{\TN}{\mathbb{N}}
\newcommand{\subsets}[1]{\mathcal{P}(#1)}
\newcommand{\setb}[1]{\left\{#1\right\}}
\newcommand{\land}{\text{ and }}
$$
Algorithms
...
- 341
Only top scored, non community-wiki answers of a minimum length are eligible