Is theta notation called the average case?

Question

There are some books which state that theta notation is called the average case while others state that theta is not the average case. If theta is not the average case then what is called the average case in respect with algorithms?

Answer 1

You are confusing two different concepts.

---

The average-case time complexity is running time averaged over all possible inputs (under some probability distribution). It is thus a function of the size of the input for a certain algorithm.

The theta-notation is just a way of describing a certain type of relationship between two functions. In particular if one function is big-Theta of the other function, this tells us that one grows approximately as fast as the other one.

---

You can use the big-Theta notation to describe the average-case complexity. But you can also use any other notation for this purpose.

If an algorithm has the average-case time complexity of, say, 3*n^2 - 5n + 13, then it is true that its average-case time complexity is Theta(n^2), O(n^2), and O(n^3). Of these three, Theta(n^2) is the most accurate description of its time complexity (but of course not as accurate as the exact expression, which in practice is nearly impossible to get; all we can usually provide is some bounds).

To summarize, the theta-notation (and all other asymptotic notations) allows you to characterize the average-case running time of your algorithm in terms of well-known functions (e.g. it grows approximately as n^2).