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
7
votes
1
answer
11k
views
What is an optimal algorithm?
I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
- 193
2
votes
3
answers
3k
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).
...
- 1,529
2
votes
2
answers
5k
views
What is the Big Theta of $(\log n)^2-9\log n+7$? [duplicate]
How can I find the Big Theta of $(\log n)^2-9\log n+7$?
I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.
- 21
2
votes
2
answers
8k
views
Proving Postorder Traversal's Time Complexity
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
...
user93381
2
votes
3
answers
340
views
How can $\Theta$ and $O$ complexities be different?
From the definition of the $\Theta$-notation,
$$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$
We can see that the ...
- 123
2
votes
3
answers
1k
views
Can I use Θ if tightest lower and upper bound are not the same?
When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation? If an algorithm has ...
- 21
3
votes
1
answer
2k
views
Is $T(n^2) = Ω(n)$?
According to this link:
We need the notation for the lower bound. A capital omega $\Omega$ notation is used in this case.
We say that $f(n) = \Omega(g(n))$ when there exist constant $c$ that $f(n) \...
- 217
1
vote
1
answer
2k
views
Time complexity - least upper bound
I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is not ...
- 263
2
votes
1
answer
1k
views
Improve minimum spanning tree with new edge, with better running time than O(|V|)?
The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ ...
- 345
1
vote
2
answers
225
views
Reasoning on Efficiency (2)
Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective ...
- 1,647
1
vote
2
answers
521
views
What is the worst-case big-O time complexity for this code?
I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so ...
- 113
1
vote
2
answers
563
views
Calculate the average Big O from a function?
I was given this function: $T(N) = 3N\log^2 N + 5N^2\log N + \log N + 17N + 2$ and was asked to find the average Big O complexity.
If the Big(O) deals with an upper bound, would this algorithm be $O(...
- 125
0
votes
1
answer
702
views
Big O understanding given different input sizes
I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
0
votes
1
answer
314
views
What is the time complexity of the piece of code given below
int IsPrime(n)
{
int i, n;
for (i=2; i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Prime \n"); return 0;}
return 1;
}
Here the loop ...
- 348
1
vote
3
answers
149
views
Ω(f(x)) and worst case analysis
I'm currently reading The Algorithm Design Manual by Steven S. Skiena as my first book to algorithms.
Something in the asymptotic part is kind of confusing to me.
Proving the Theta
The analysis above ...
- 235