Linked Questions
39 questions linked to/from How do O and Ω relate to worst and best case?
1
vote
1
answer
6k
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 ...
- 149
-1
votes
2
answers
286
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 ...
- 141
3
votes
1
answer
1k
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.
...
user87772
3
votes
2
answers
351
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$?
- 43
0
votes
1
answer
214
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
1
vote
1
answer
479
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 ...
- 3,090
1
vote
1
answer
146
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:
...
- 281
2
votes
1
answer
71
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 ...
- 21
0
votes
0
answers
59
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 ...
- 476
0
votes
0
answers
58
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)$ ...
- 155
197
votes
3
answers
27k
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 ...
- 72.9k
101
votes
3
answers
35k
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 ...
- 1,323
6
votes
4
answers
5k
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)$ ...
- 61
6
votes
4
answers
5k
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))$...
- 243
3
votes
5
answers
13k
views
What is the big-O of the function 2 log(log n) + 3 n log(n) + 5 log(n)?
What is the big-O of the function $2\log(\log(n)) + 3n\log(n) + 5\log(n)$?
Is it just $O(n\log(n))$ for the whole function? I'm not sure how to represent $2\log(\log(n))$.
- 41