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

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

### How do O and Ω relate to worst and best case?

Consider the following algorithm (or procedure, or piece of code, or whatever): ...
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 ...
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 ...
Accepted

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

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

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

### 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)$. ...
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 ...

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

### 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 ...
### What is the meaning of $O(m+n)$?
Part 2 $$\newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}{\mathcal{P}(#1)} \newcommand{\setb}{\left\{#1\right\}} \newcommand{\land}{\text{ and }}$$ Algorithms ...