# Tag Info

Accepted

### Time complexity $O(m+n)$ Vs $O(n)$

Yes: $n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$ For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things -...
• 10.7k
Accepted

### Are there any functions with Big O (Busy Beaver(n))?

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an ...
• 268k
Accepted

• 3,497
Accepted

### Does big-Oh impose an ordered partition on the set of the "usual" functions?

This was shown by Hardy in his monograph Orders of Infinity.
• 268k
Accepted

### Upper bounds for a binomial coefficient

The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows: $$\binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k$$ Where the equality \$\sum_{i=0}^{k}...
• 22.6k