# Tag Info

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,292

### 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,681
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: ...
• 2,052

### 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 ...
• 431

• 221

### 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 ...
• 431
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 ...
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 ...
• 277k

### 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 ...
• 39k

### 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 ...
• 81.7k
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 ...
• 277k

### 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,704
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 ...
• 72.4k

• 766
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 ...
• 81.7k

### 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

### 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 ...
• 213