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,222
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 ...
- 81k
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,671
33
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,967
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
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 $...
- 81k
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 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 ...
- 381
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.4k
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 ...
- 81k
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
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 ...
- 273k
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 ...
- 37.3k
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 ...
- 81k
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,584
9
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
...
- 381
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.4k
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 ...
- 71.6k
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.3k
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 ...
- 71.6k
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,127
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 ...
- 273k
8
votes
Is Ω(f+g) = Ω(min(f,g))?
Assuming $f,g > 0$, we have
$$\max(f(x),g(x)) < f(x) + g(x) \leq 2\max(f(x),g(x)).$$
Therefore $\Theta(f(x) + g(x)) = \Theta(\max(f(x),g(x)))$, in the sense that both sets of functions are equal....
- 273k
8
votes
What does Θ(1) memory mean?
Constant space complexity of algorithm
Amount of memory your algorithm uses is independent of input.
An algorithm is said to have constant space complexity if it makes use of fixed amount of space....
- 476
8
votes
big-O and Θ notation subset
Lets refactor and reword these statements for ease of thought.
Let $A(n)$ be $Θ(g(n))$.
Let $B(n)$ be $O(g(n))$.
Note that $A$ implies $B$ because $A$ is stronger than $B$.
This means for $A$ to ...
- 216
8
votes
Can you operate on and draw conclusions on functions described asymptotically?
For some operations, such as addition, multiplication, you can operate directly on the asymptotic notation. For example, if $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, then $...
- 756
8
votes
Accepted
What does $n^{O(1)}$ mean?
It's short-hand for "$n^{f(n)}$ for some function $f(n)\in O(1)$". In other words, the function is at most $n^c$ for some constant $c$.
You can see this by directly substituting the ...
- 81k
8
votes
How did they cancel out O-terms in this fraction?
The real power of $O$ notation is in formulas like this. By systematically applying valid rules of manipulation, we can harness our intuition in a fully rigorous way, without much effort (such as that ...
- 289
8
votes
Summation of asymptotic notation
You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants.
Consider the following example: $f_i(n) = i\cdot ...
- 2,288
Only top scored, non community-wiki answers of a minimum length are eligible