3k views

### What is the difference between Big-O and worst-case run time? [duplicate]

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 ...
186 views

### What does Big O notation actually specify? [duplicate]

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 ...
248 views

### Time Complexity $\Theta$ vs. $\Omega$ [duplicate]

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$?
495 views

### What is the relationship/difference between best/worse/expected case and big O/omega/theta? [duplicate]

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

### Why is O notation the worst case? [duplicate]

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 ...
100 views

### Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case [duplicate]

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 ...
60 views

### Use of Big-Oh in Worst case [duplicate]

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 ...
40 views

### Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n)) [duplicate]

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: ...
51 views

### Why worst case running time of Insertion sort is $\Theta(n^2)$ [duplicate]

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 ...
41 views

### $\Omega$-notation for insertion sort [duplicate]

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)$ ...
18k views

### Is there a system behind the magic of algorithm analysis?

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 ...
25k views

### How does one know which notation of time complexity analysis to use?

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 ...
3k views

### Big Oh vs Big Theta

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))$...
### Why do we use big O rather than $\Omega$ when discussing best case runtime?
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 would like to know why the following statement The running time of algorithm $A$ is at least $O(n^2)$ which means the best-case running time of $A$ is $O(n^2)$ is meaningless (CLRS page 53). ...