Linked Questions

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 ...
Cow Pow Pow's user avatar
-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 ...
cade galt's user avatar
  • 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. ...
user avatar
3 votes
2 answers
350 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$?
MNRC's user avatar
  • 43
0 votes
1 answer
213 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 ...
Lars17S's user avatar
1 vote
1 answer
443 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 ...
Charlie Parker's user avatar
1 vote
1 answer
121 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: ...
rsonx's user avatar
  • 281
1 vote
1 answer
69 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 ...
sam's user avatar
  • 11
0 votes
0 answers
58 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 ...
Prateek's user avatar
  • 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)$ ...
E. Shcherbo's user avatar
197 votes
3 answers
26k 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 ...
Raphael's user avatar
  • 72.6k
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 ...
Miles's user avatar
  • 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)$ ...
agcha's user avatar
  • 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))$...
iart's user avatar
  • 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))$.
ALute's user avatar
  • 41

15 30 50 per page