37 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 -...
user avatar
  • 10.7k
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 ...
user avatar
28 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 = \...
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. ...
user avatar
  • 32.8k
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 ...
user avatar
  • 2,281
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{...
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 ...
user avatar
  • 13.6k
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)) = \...
user avatar
  • 6,942
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 ...
user avatar
  • 5,144
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 ...
user avatar
  • 22k
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$
user avatar
  • 2,281
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)$ ...
user avatar
  • 595
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 ...
user avatar
  • 211
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 ...
user avatar
  • 4,889
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 ...
user avatar
  • 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 ...
user avatar
  • 2,154
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 ...
user avatar
  • 2,281
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$,...
user avatar
  • 22.6k
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 ...
user avatar
  • 13.1k
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$.
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 ...
user avatar
6 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 $$ \...
user avatar
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 ...
user avatar
  • 163
6 votes

How can $\Theta$ and $O$ complexities be different?

If the $O$-complexity given is true, then $f(x)\leq c_2n\log n$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity? Yuval has covered the quicksort ...
user avatar
5 votes

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

You can write $O(f)$ for any function $f$ and it makes perfect sense. As per the definition, $g(n)=O(f(n))$ if there is some constant $c$ such that $g(n)\leq c\,f(n)$ for all large enough $n$...
user avatar
5 votes
Accepted

Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

From this post, you can approximate $\log(1+x)$ with $x$ for little values of $x$. Hence, $$ f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1 $$ Therefore, you can't find any constant $c$, such that $f(...
user avatar
  • 3,497
5 votes
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.
user avatar
5 votes
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}...
user avatar
  • 22.6k
5 votes
Accepted

Big O vs. Big Theta for AVL tree operations

This is a pedantic point which I suggest ignoring. The intended interpretation of the "worst case" column seems not to be the worst-case complexity, but rather bounds on the complexity which ...
user avatar

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