107

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$. Note that this also clarifies some caveats of the $O$ notation. For example, we write that $(1/2) n^2 + ...


76

You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement. $f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the ...


60

This algorithm can be re-written like this Scan A until you find an inversion. If you find one, swap and start over. If there is none, terminate. Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the ...


53

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 they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.


48

If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions. If $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then $c=0 \qquad \ \,\iff f \in o(g)$, $c \in (0,\infty) \iff f \in \Theta(g)$ and $c=\infty \quad \ \ \ \iff f \in \omega(g)$. With this, you should be able to order most of the ...


44

This is largely piggy-backing on the answers already posted, but may offer a different perspective. It's revealing that the question discusses "sufficiently small values of n". The whole point of Big-O is to describe how processing grows as a function of what's being processed. If the data being processed stays small, it's irrelevant to discuss the Big-O, ...


43

Big O: upper bound “Big O” ($O$) is by far the most common one. When you analyse the complexity of an algorithm, most of the time, what matters is to have some upper bound on how fast the run time¹ grows when the size of the input grows. Basically we want to know that running the algorithm isn't going to take “too long”. We can't express this in actual time ...


43

$O$ is a function $$\begin{align} O : (\mathbb{N}\to \mathbb{R}) &\to \mathbf{P}(\mathbb{N}\to \mathbb{R}) \\ f &\mapsto O(f) \end{align}$$ i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic bound of (at most) $f$. And strictly speaking the correct notation is thus $$ (n \mapsto T(n)) \in O(n\mapsto f(n)) $$ ...


39

Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$. Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on.. Per se, the two have nothing to do with ...


39

No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$. Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input. Note that the running time is a count of the number of instructions executed by the algorithm, so ...


35

Converting Full History to Limited History This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence $$ T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big) $$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...


33

NO. Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation. (This is reference [1] in the paper by Dietz that you mention in your first comment.) The lower bound holds in the very powerful cell probe model of computation, which only considers the number of ...


33

You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables. Simply speaking, since $$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$ you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent ...


28

Generating Functions $\newcommand{\nats}{\mathbb{N}}$ Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked. This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...


27

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 = \emptyset$, then $\Theta(f)=\Theta(g)$. Moreover, $\Theta(f)\subseteq O(f)$. Why do they relate to each other the way they do? The explanation is probably ...


25

Believe it or not, it seems (in my experience) that many algorithms people have actually not thought about what the big O notation formally means, and when asked about it, you can get several different answers. Some issues are discussed in the paper On Asymptotic Notation with Multiple Variables by Rodney R. Howell. Curiously, it also seems that most ...


25

Although it's not quite an answer to your question, the Boyer-Moore string search algorithm comes close. As Robert Moore says on his web page about the algorithm, Our algorithm has the peculiar property that, roughly speaking, the longer the pattern is, the faster the algorithm goes. In other words, generally speaking the algorithm searches for an ...


25

The issue comes down to ambiguous terminology. $(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative. Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}...


23

Speaking from experience, when trying to figure out the growth rate for some observed function (say, Markov chain mixing time or algorithm running time), it is very difficult to tell factors of $(\log n)^a$ from $n^b$. For example, $O(\sqrt{n} \log n)$ looks a lot like $O(n^{0.6})$: [source] For example, in "Some unexpected expected behavior results for ...


22

To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size. For instance, we say that a function that takes $3n$ steps is $O(n)$, because, ...


21

Not every pair of functions is comparable with $O(\cdot)$ notation; consider the functions $f(n) = n$ and $$ g(n) = \begin{cases} 1 & \text{if $n$ is odd}, \\\ n^2 & \text{if $n$ is even}. \end{cases} $$ Moreover, functions like $g(n)$ do actually arise as running times of algorithms. Consider the obvious brute-force algorithm to determine ...


21

Master Theorem The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is ...


21

All orders of magnitude involve a constant $C$, several of them actually. When the number of items are large enough that constant is irrelevant. The question is whether the number of items is small enough for that constant to dominate. Here's a visual way to think about it. All have a startup constant which determines their starting point on the Y axis. ...


20

Another tip: sometimes applying a monotone function (like log or exp) to the functions makes things clearer.


20

Saying that a big-O bound is "asymptotically tight" basically means that the author should have written $\Theta(-)$. For example, $O(x^2)$ means that it's no more than some constant times $x^2$ for all large enough $x$; "asymptotically tight" means it really is some constant times $x^2$ for large enough $x$ and not, say, some constant ...


18

In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely not be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.


18

Consider the following algorithm (or procedure, or piece of code, or whatever): Contrive(n) 1. if n = 0 then do something Theta(n^3) 2. else if n is even then 3. flip a coin 4. if heads, do something Theta(n) 5. else if tails, do something Theta(n^2) 6. else if n is odd then 7. flip a coin 8. if heads, do something Theta(n^4) 9. else if ...


18

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{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n. $$ Using Stirling's approximation we can get more refined asymptotics, but we ...


17

Typically $O$ is used for stating upper-bounds (an estimate from above), while $\Omega$ is used to state lower-bounds (an estimate from below), and $\Theta$ is used when they match, in which case you can use $\Theta$ in place of them (usually) to state the result.


17

Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual: $$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$ \gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$ Here $\alpha(n)$ denotes the inverse Ackermann function.


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