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.
Binary Search
Searches for an element in a sorted array in $O(log(n))$ time.