Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Spring 2022 -- CSC 2700 Section 01 (1216 Patrick Taylor, 6:30 PM - 8:20 PM)



Big O

Big O is a topic that is often stressed in Computer Science. Many students walk away from a Big O lecture with a fuzzy (at best) understanding.

So lets spend some time trying to explain what Big O is and what it is not. Big O is not a way to compare the absolute speed or run time of multiple programs. It is not a magic bullet that will enusre your code is fast enough.

Big O does provide a way to compare "relative" efficiency of multiple algorithms. It does this by ignoring the discrete computaions (and their run time) and instead looks at how many times something will be done. At first glance, Big O may seem very arbitrary.

Big O attempts to classify how many times your code will repeat a computation and then take that and match it to a list of known measurements (called Complexity Classes). The goal most of the time is to determine the Big O (Complexity Class) of a series of algorithms and then choose to implement the algorithm with the simplest (hence fastest) complexity. Here is the list of Complexity Classes (from simplest/fastest to most complicated/slowest):

Determing Big O is the process of examing an algorithm, determing its most complex area and then classifying that complexity.

The above statement is important. If an algorithm has multiple phases/sections, you examine each section. The Big O of the algorithm is the Big O of the most complex section. At first this does not seem to make sense, but think about it. If an algorithm has several sections such as this:

  1. loop O(n)
  2. loop O(n2)
  3. loop O(n)
You might be inclined to think the Big O of the algorithm is O(n) + O(n2) + O(n) or O(n2) + 2 * O(n). For large values of n, 2 * O(n) is much smaller than O(n2). Since the goal of Big O is to determine a rough approximation, the smaller part is ignored and the Big O of the algorithm is O(n2).

The above information is heavily influenced by the first part of chapter 2 (pages 17-20) of the Competitive Programmers' Handbook