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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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): ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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(...
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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)$. ...
user avatar
  • 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 ...
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^...
user avatar
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 ...
user avatar
  • 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 ...
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 ...
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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(\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 341

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