Linked Questions

Big-O describes an upper bound on run time. Is that not the definition of "worst-case"? For example, how can we say that a hash table insertion require O(1) time on average? Constant time is the best ...

Regarding time complexity I've read conflicting things: 1) That it is worst case. 2) That is average case. For example if I want to know the time complexity for inserting into an arbitrary point in ...

In the big O section of Cracking the Coding Interview 6th edition, I read the following. ...

If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?

I don't understand why O notation is the worst case. If this notations describes a function f such that 0 <= f(n) <= cg(n), we can see that in any case f will be smaller that the original ...

I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most ...

If it is given that a program has a worst case running time of $O(n)$, then is it still okay to define the running time as being $O(n^2)$. By definition, this seems corrects since Big-Oh is ...

I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms. The book explained the three asymptotic notations literally very well. However, there was this paragraph: ...

From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Theorem 3.1 For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if ...

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...

On the course material I am following we have been given an explanation for theta as being when omega and Oh 'sandwich' the run time, so it is bounded between the two values, at least I think this is ...

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ ...

I mathematically understand $f(n) \in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $\exists c, n_0$ s.t. $f(n) \leq cg(n) \forall n \geq n_0$. Similarly, $f(n) \in \Theta(g(n))$...