This lecture discusses the Big-O Notation and Binary Search.

Big-O Notation

Big-O notation is used to describe the order of growth of many types of things. In CS2040S, we use it to describe time complexity of algorithms.

Note that:

  • $O(f(n))$ describes the upperbound of the growth of $f$, i.e. the worst case-time complexity;

  • $\Omega(f(n))$ describes the lowerbound of the growth of $f$, i.e. the best-case time complexity;

  • $\Theta(f(n))$ describes is best approximation of the order of growth of $f$, i.e. the average time complexity.

Searches for an element in a sorted array in $O(log(n))$ time.