54 votes
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 ...
Roukah's user avatar
  • 771
39 votes
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 -...
nir shahar's user avatar
  • 11.6k
37 votes
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 ...
Yuval Filmus's user avatar
29 votes
Accepted

Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Is what I wrote about big-O correct? Yes. How do big-Theta sets relate to each other, if they relate at all? They are a partition of the space of functions. If $\Theta(f)\cap \Theta(g)\not = \...
Tom van der Zanden's user avatar
21 votes
Accepted

Are there variations of the regular runtimes of the Big-O-Notation?

I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect. Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations. ...
John L.'s user avatar
  • 39k
20 votes
Accepted

Can I multiply Big-O time complexities?

Yes, you can and yes, it is. Considering, for example, the non-negative case, we have a more general property: $$O(f)\cdot O(g) = O(f\cdot g )$$ Let's take $ \varphi \in O(f) \cdot O(g) $. Then we ...
zkutch's user avatar
  • 2,364
18 votes
Accepted

Asymptotics question

We have $$ \frac{n!}{(n/2)!(n/4)!\cdots 2!} = \frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\ \binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{...
Yuval Filmus's user avatar
17 votes

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

linearithmic: adj. Of an algorithm, having running time that is O(N log N). Coined as a portmanteau of ‘linear’ and ‘logarithmic’ in Algorithms In C by Robert Sedgewick (Addison-Wesley 1990, ISBN ...
miracle173's user avatar
16 votes

Does it make sense to say Big Theta of 1? Or should we just use Big O?

Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a ...
vonbrand's user avatar
  • 14k
15 votes
Accepted

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

To prove or disprove this kind of equality with $\mathcal{O}$, you need to go back to the definition of $\mathcal{O}$ with inequalities. For example, let's study the question $\log(\mathcal{O}(n)) = \...
Nathaniel's user avatar
  • 15.6k
14 votes

Does it make sense to say Big Theta of 1? Or should we just use Big O?

vonbrand's answer is correct in general, but let me add that if $\boldsymbol{f(n)}$ is the running time of an algorithm, then you are correct, $\boldsymbol{O(1)}$ and $\boldsymbol{\Theta(1)}$ are the ...
Caleb Stanford's user avatar
14 votes

Time Complexity of Linear Search vs Brute Force

Time complexity is expressed as a function of some parameter, which is usually the size of the input. The combination lock is not a perfect analogy as it is not immediately clear what the input would ...
Steven's user avatar
  • 29.5k
13 votes

Are there variations of the regular runtimes of the Big-O-Notation?

You are always free to not use this notation at all. That is, you can determine a function $f(n)$ as precisely as possible, and then try to improve on that. For example, you might have a sorting ...
Juho's user avatar
  • 22.6k
13 votes

Arrange in increasing order of asymptotic complexity

You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$
zkutch's user avatar
  • 2,364
12 votes

Can I multiply Big-O time complexities?

It's an abuse of notation. $O(n)$ is a set of functions. So $O(n)*O(n)$ is not really defined. $O(n)\times O(n)$ is defined, but it is defined as cartesian products of the set of functions in $O(n)$ ...
Taemyr's user avatar
  • 605
11 votes

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

I've always heard O(n log n) described as "log-linear" which seems about right to me.
Dylan Skola's user avatar
11 votes

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

Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the ...
BBrooklyn's user avatar
  • 211
9 votes
Accepted

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

Yes. Your understanding is correct on all points!
D.W.'s user avatar
  • 159k
8 votes

Are "of the order of n" and "Big O" the same thing?

"On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of ...
dkaeae's user avatar
  • 5,017
8 votes

Are there variations of the regular runtimes of the Big-O-Notation?

While the accepted answer is quite good, it still doesn't touch at the real reason why $O(n) = O(2n)$. Big-O Notation describes scalability At its core, Big-O Notation is not a description of how long ...
Christian Legge's user avatar
8 votes

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

The difference is IMHO well explained in that book, the part you are referring to says The number of anonymous functions in an expression is understood to be equal to the number of times the ...
Doc Brown's user avatar
  • 213
8 votes

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

Doc Brown answered your first question perfectly. Let me answer your second question. The expression $O(i)$ is a placeholder for a function which is bounded by $Ci$ for some $C > 0$. Therefore $$ \...
Yuval Filmus's user avatar
8 votes

Summation of asymptotic notation

You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants. Consider the following example: $f_i(n) = i\cdot ...
Tassle's user avatar
  • 2,522
8 votes
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 ...
zkutch's user avatar
  • 2,364
8 votes

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$,...
Steven's user avatar
  • 29.5k
8 votes

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^...
gnasher729's user avatar
7 votes

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....
miracle173's user avatar
7 votes

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 ...
Ariel's user avatar
  • 13.4k
7 votes

$(\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$.
Pratik Haware's user avatar
7 votes
Accepted

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 ...
Emil Jeřábek's user avatar

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