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 ...
- 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 -...
- 11.5k
36
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 ...
- 274k
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 = \...
- 13.1k
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.
...
- 38.5k
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 ...
- 2,356
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{...
- 274k
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 ...
- 542
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 ...
- 13.9k
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)) = \...
- 12.3k
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 ...
- 6,873
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 ...
- 27.4k
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 ...
- 22.4k
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$
- 2,356
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)$ ...
- 595
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.
- 121
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 ...
- 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.♦
- 154k
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 ...
- 4,979
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 ...
- 181
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 ...
- 2,288
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 ...
- 2,356
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$,...
- 27.4k
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^...
- 27.8k
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....
- 542
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 ...
- 13.3k
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$.
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 ...
- 955
7
votes
Time Complexity of Linear Search vs Brute Force
You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying ...
- 456
6
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 ...
- 163
Only top scored, non community-wiki answers of a minimum length are eligible