Asymptotic Notations 2/2

How to pronounciate the evaluation?

Speaking about the first case candies problem, we may say: In the worst case, the complexity will be O(n) (n - the number of candies).

Speaking about the second case candies problem, we may say: In the worst case, the complexity will be O(n log n) (because it is a Binary Search algorithm; we will talk about that later).

There are a lot of evaluations that show the limits of time complexity.

O-little (o(n)), for example, is used to describe an upper bound that cannot be tight. Omega notation (Ω(n)) represents the lower bound of the running time of an algorithm.

By exploring the picture, we can decide which time complexity is the best for the algorithm and which is the worst.

As we decided earlier, sometimes we have a choice to buy a more expensive washer machine (O(n)) or cheaper (O(n log n), for example). There are many cases where we have only one possible way to cope with the problem, so we need to buy that only one washing machine.

Best, worst, average

Mostly used. Best case (Big-O or O(n) )is the function which performs the minimum number of steps on input data of n elements.

Worst case (Omega or Ω(n)) is the function which performs the maximum number of steps on input data of size n.

Average case (Theta or θ(n)) is the function which performs an average number of steps on input data of n elements.