# Tag Info

Accepted

### What is the name the class of functions described by O(n log n)?

It's called linearithmic time, and is a special case of a more general class known as quasi linear. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact ...
• 771
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 -...
• 11.6k
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 ...
• 277k
Accepted

• 2,522
Accepted

### Isn't linear time O(n)?

Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$. When the presenter is speaking about linear time for ...
• 2,364

### What are you allowed to move into the big O notation for it to be still correct?

In order for $f(O(n)) \in O(f(n))$ to hold you essentially want $f$ to satisfy $f(cn) \le df(n)$ where $n$ is sufficiently large. Here the inequality must hold for all sufficiently large constants $c$,...
• 29.5k

### Is Big-Theta a more accurate description of worst case run time than Big-O?

O(f(n)) is also used when there is no simple function that your runtime is close to. For example: Find the smallest prime factor of n by trial division, finishing when a factor is found: There are O(n^...
• 30k

### What is the name the class of functions described by O(n log n)?

This was too long for a comment, so I wrote an answer. I did not add this to my first answer because a lot of people already upvoted my first vanswer and I am not sure they agree with this answer, too....
• 542

### Is squaring easier than multiplication?

Observe that $ab=\frac{1}{2}\left((a+b)^2-a^2-b^2\right)$, hence multiplication requires three squaring operations and 3 additions/subtractions (division by 2 is easy), which means squaring is ...
• 13.4k
### $(\log n)^{\log n}$ lower-bound and upper-bound
Here is a way to show it without limits. Let $n = 2^x$. Now you are comparing the growth rates of $2^x$ and $x^x$.
### How does $Θ(\log(n!))=Θ(\log(n^n)$?
As a matter of fact, $$\lim_{x\to \infty}\frac{\log_2(x^x)}{\log_2(x!)}=1.$$ So there is no problem to reconcile. Looking at the first revision of the question, it seems to me that you are confused ...