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 ...
Vincenzo's user avatar
  • 3,292
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 ...
leftaroundabout's user avatar
38 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: ...
manlio's user avatar
  • 2,052
16 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 ...
kaba's user avatar
  • 431
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(...
Anatolii's user avatar
  • 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 ...
Joey Eremondi's user avatar
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 ...
David Richerby's user avatar
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^...
Eric Duminil's user avatar
11 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 ...
kaba's user avatar
  • 431
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 ...
Gilles 'SO- stop being evil''s user avatar
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 ...
Yuval Filmus's user avatar
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 ...
John L.'s user avatar
  • 39k
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 ...
David Richerby's user avatar
10 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 ...
Yuval Filmus's user avatar
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 ...
Mario Cervera's user avatar
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 ...
Raphael's user avatar
  • 72.4k
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(\...
Ariel's user avatar
  • 13.4k
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 ...
Alexey Romanov's user avatar
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....
Prateek's user avatar
  • 476
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 $...
PSPACEhard's user avatar
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 ...
David Richerby's user avatar
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 ...
ShreevatsaR's user avatar
8 votes

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

The difference is IMHO well explained in that book, the part you are referring to says The number of anonymous functions in an expression is understood to be equal to the number of times the ...
Doc Brown's user avatar
  • 213
8 votes

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

Doc Brown answered your first question perfectly. Let me answer your second question. The expression $O(i)$ is a placeholder for a function which is bounded by $Ci$ for some $C > 0$. Therefore $$ \...
Yuval Filmus's user avatar
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 ...
Tassle's user avatar
  • 2,522
7 votes

Why are Complexity Notations Called Asymptotic?

I would like to quote from "Concrete Mathematics" (Chapter 9) by Ronald Graham, Donald Knuth, and Oren Patashnik. It does mention curves and asymptotes. The word asymptotic stems from a ...
hengxin's user avatar
  • 9,551
7 votes
Accepted

Is $\log(n!)$ in $\Theta(n \log(n))$?

You mentioned $$ \log(n!) = \log(n(n-1)\cdots1) = \log(n)+\log(n-1)+ \cdots +\log(1) $$ From this, we can write (assuming $\log$ is base 2) $$ \begin{array}{l} \log(n!) \\ = \log(n)+\log(n-1)+....+\...
chi's user avatar
  • 14.6k
7 votes

Landau Notation: Why is O(f) (not) the set all g < c*f?

There are at least three fundamental misunderstandings, here. $O(\cdot)$ only makes statements about large enough inputs to the function. It's not that there exists some $c$ such that $g\leq c\,...
David Richerby's user avatar
7 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 ...
rp.beltran's user avatar
7 votes

Conflicting definitions of quasipolynomial time

Both definitions are equivalent, since when we say that a problem can be solved in time $t$, we usually mean that it can be solved in time at most $t$. For example, a problem can be solved in time $n$ ...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible