Big O or Big Θ?

Question

I know the difference of Big O and Big Θ, but I can find few cases where I really need to use Big O or Big Ω instead of Big Θ.

When the algorithm and also the case of running time complexity (average, worst and best) are given, we can measure the running time of the algorithm and state it as Θ. (Please notice algorithm means a clear and step by step solution for a problem, correct me if I am wrong)

On one hand just saying the running time of an algorithm without specifying the case complexity is ambiguous. On the other hand if it refers to one of these cases then the Big O and Big Ω lose their application, because we are specific on the case and at most or at least lose their meaning there. We simply can calculate the T(n) or use Θ if we want to be rough.

For example the time of quick sort algorithm in average case is Θ(n lg n) and in worst case is Θ(n^2) (as we can calculate the time T(n)). However, some may specify them with O(n log n) and O(n^2), but the Θ is also correct and more precise.

Then how or why should we use O or Ω for the running time of this algorithm? Please don't forget to include the answer to this specific instance.

I don't look for explanation of them, just some real examples that we really need Big O and not Big Θ.

Answer 1

partial small answer

Use Θ when it is known because it conveys at the same time a message about O and Ω. Still you are doubling your chances of being incorrect like I did in the comments. When It is not known use Ω

Long answer

It doesnt matter. What is measured, the big O notation, the case analysis are orthogonal dimensions in the same problem space.

• You can do worst case time analysis and limit to the upper bound O
• You can do best case space analysis and provide O and lower bound Ω
• You can do amortized case time analysis and provide O and Ω, which turn out to be the same thus providing a tighter bound Θ.

Now providing upper bounds of the running time in worst case is the most popular type of analysis.

Note:

If you are given an homework, it should state something like

what is the worst case time complexity of this algorithm in terms of O.

If you are solving a real world problem, you infer these from the problem itself. If your program is killed because it uses too much memory, it doesn't make sense to do a running time complexity analysis.

To be straight, which notation (O, Θ or Ω) and which time we should use for the time of the quick sort algorithm, why?

What is the rationale behind (O, Θ or Ω)?

Let say we have a interesting problem like matrix multiplications. People find out that multiplying matrices will help in several applications, so they start looking for algorithms.

1. The average joe alg. designer find an algorithm which is O(n^3), using the naive method. It is not that inefficient so he moves on.
2. Next Strassen find out that it can be improved to O(n^2.807)
3. Now people start to ask if it be can improved further.
4. A part of this question is how further ?. To reply, you need to provide lower bounds Ω. the higher the better. One bound is Ω(n^2). A specific bound of Ω(n^2 log(n)). They are not demonstrated by providing algorithms but can be deduced from the problem statement.
5. Now as an algorithm designer, if you hit a complexity of upper bound O(n^2 log(n)) for matrix computation you know you hit the jackpot. When you hit the jackpot, you start using Θ to convey two messages at once.
6. Because nobody has hit the jackpot yet,people express new findings in matrix multiplication algorithms in better upper bounds, like O(n^2.237)

An example of different lower bound in worst case - reallocation in arrays

Let's say you implement a set using an array. To insert a element you simply put in the next available bucket. If there is no available bucket you increase the capacity of the array by a value m.

For the insert algorithm "there is no enough space" is the worse case.

 insert (S, e)
   if size(S) >= capacity(S) 
     reserve(S, size(S) + m)
   put(S,e)

Assume we never delete elements. By keeping track of the last available position, put, size and capacity are Θ(1) in space and memory.

What about reserve? If it is implemented like realloc in C, in the best case you just allocate new memory at the end of the existing memory (best case for reserve), or you have to move all existing elements as well (worse case for reserve).

• The worst case lower bound for insert is the best case of reserve(), which is linear in m if we dont nitpick. insert in worst case is Ω(m) in space and time.
• The worst case upper bound for insert is the worse case of reserve(), which is linear in m+n. insert in worst case is O(m+n) in space and time.

Answer 2

Big O and best / average / worst look at different aspects of execution speed.

---

Big O / Big Θ do not say how long some code takes to run.
It says how running time depends on input size.

Actual time depends on a variety of factors, almost all of which are ignored. (see footnote below)

Best / worst / average / typical is a completely different look on running time. They are (usually) more specific than Big O notation - but often the times are given in Big(O):

The typical time for a hash table lookup is O(1). The worst case is O(N)

Note that this statement is technically incorrect: Big O does not specify a time. A pedantic version of that statement would be:

In the typical case, the time to look up one element is more or less independent of the number of item in the hash table (O(1)). Worst case, lookup time grows proportional with the number of items in the table (O(N)).

---

Footnote:

Big O notation even ignores all but the fastest growing term.

If you have two algorithms with deterministic run times

tA(N) = 10s * N^2 + 1s * N + 42 days 
tB(N) = 1 day * N^2 

Both would be O(N^2)

Even though the second is clearly worse for large N, this is not expressed in Big O.

Keep in mind that while run time is the most common use for Big O notation, it can as well be used for memory usage, or particular operations such as disk access or swaps.

---

Regarding your update:

what the 'running time of the algorithm' refers to, when the case is not specified? Does it refer to the running time of the algorithm in worst case? average case or best case?

Formally: if it's not specidfied, it's not specified.

Informally, whatever makes most sense in the given context. If nothing is specified, most people will assume it is average or at least the typical case - but how far you rely on that is up to you.

Partition sort:

Formally, without specifying the case, - Any O(f(N)) >= O(N^2) is formally correct without specifying the case. Even O(N^N) would be correct, just not useful. - ditto for any Ω(f(N)) <= O(n lg n)

Specification

What needs to be specified depends on the context.

An API will usually specify as little as it can get away with, to leave flexibility for implementation. E.g. it might specify "retrieval is in amortized constant time", meaning an O(1) typical case with worst case being unspecifiedly worse but occuring rarely.

An API will also usually only specify Big O, unless there is a particular reason for faster being worse (such as side channel attacks).

On the other end, a full specification would specify the algorithm sufficiently that you can calculate O and Ω for all cases yourself - as well as more. As said before, Big O/Ω can be insufficient to make an informed decision about runtime behavior.

Inbetween, whatever is needed:

• Generally, O is more common than the others because Ω is almost never relevant, and Θ is not always available.

• If only one value is specified it's usually average or typical time, because that allows to judge the "value" of the algorithm.

• If two values are specified, it's worst case additionally, because the latter is the most common criterion when either comparing algorithms with identical typical behavior, or you have real time requirements.

• The next thing would be the conditions under which performance degrades. Because an algorithm that is "O(N) typical, O(N^2) for one in a million inputs" is something completely different from "O(N) typical, O(N^2) on monday mornings".

• If this is still insufficient, you will usually see a maximum number of particular operations, such as "at most N^2+1 comarisons and N/2-1 swaps".

Answer 3

So both theta, and O, unless otherwise stated, generally refer to the average running time of an algorithm. Therefore, partition sort, is both O(nlogn) and theta(nlogn).

The reason that they are different is that sometimes it can be quite easy to see/prove that the average case is not worse than some function, but it can still be difficult to prove what its running time is on average, or in some cases, to prove what is an optimal running time.

For example, when multiplying matrices its clear that you can have a O(n^3) algorithm, since that is how you would do it by hand. The best known algorithm is theta(n^2.4), roughly. However, some other mathematicians have claimed that the lower bound on an algorithm is Omega(n^2 log n), and yet other researchers claim that is wrong, and that a theta(n^2) algorithm exists.