Linked Questions
35 questions linked to/from How do O and Ω relate to worst and best case?
1
vote
1answer
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 ...
-1
votes
2answers
180 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 ...
3
votes
2answers
238 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$?
2
votes
1answer
438 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.
...
1
vote
1answer
59 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 ...
0
votes
1answer
42 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 ...
1
vote
1answer
84 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 ...
0
votes
0answers
50 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 ...
1
vote
1answer
37 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:
...
0
votes
0answers
39 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)$ ...
163
votes
3answers
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 ...
93
votes
3answers
24k 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 ...
6
votes
4answers
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))$...
2
votes
3answers
924 views
Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared?
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).
...
4
votes
3answers
2k views
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)$ ...