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

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

• 261

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

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

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

• 13.3k
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

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

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

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