When computer scientists wanted to find out how to compare the speeds of algorithms on computers, the "old-fashioned" way of doing things was to count the number of instructions, and evaluate an exact formula for a given algorithm. This came with some troubles though; in practical computing it is very difficult to measure the exact speed of an algorithm from one computer to the next, and in the earlier days of computing, processing power was doubling every 18 months in accordance with <a href="https://computer.howstuffworks.com/moores-law.htm" target="_blank" style="color:inherit">Moore's law</a> (which <a href="https://www.technologyreview.com/s/601441/moores-law-is-dead-now-what/" target="_blank" style="color:inherit;">might not be true</a> anymore). An algorithm that ran in some amount of time on one person's computer might be wildly different on another's computer.

What computer scientists needed was a way to generalize the amount of time that an algorithm would take to complete, and that is where Big-O Notation came about.

Assumptions

  • Comfortable with algebraic expressions

What Is Big-O Notation?

Big-O notation, "Big-Oh", is a mathematical notation used in computer science that describes the complexity — and performance — of an algorithm.

Big-O is an excellent way to generalize the growth of an algorithm as the amount of data to process grows arbitrarily large, usually denoted as being of size n.

A more formal definition of an algorithm being "Big-O of n" is:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">f(n) = O(g(n)) if f(n) grows no faster than g(n). </div> <br>

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Alg_BigO_01.png" alt="big-o notation graph reference" style="width:300px;max-width:95%;"> </div>

> "grows no faster than" means that an algorithm that takes O(n) time to complete also takes O(n<sup>2</sup>) time, however O(n) is more valuable to a computer scientist as it is closer to the actual growth rate of the function.

Usually, an algorithm will be evaluated for it's worst-case performance, however, average-case is also very important as it describes how a given algorithm performs in the real world.

An algorithm is said to be optimal if its execution time can be mathematically proven to be as fast as it will ever be in respect to Big-O notation.

Rules for deducing Big-O

There are a few steps to follow when evaluating what the Big-O of an algorithm is. To start, determine what variable (if any) has an effect on the overall time an algorithm will take and look for loops, recursions, and other factors that affect the algorithm. Once you have a general equation, do the following:

  1. Omit any multiplicative constants; 4n becomes n.
  2. If a factor has a higher power, remove all smaller powers; n<sup>2</sup> + n becomes n<sup>2</sup>.
  3. Any exponential dominates any polynomials: 2<sup>n</sup> + n<sup>2</sup> becomes 2<sup>n</sup>.
  4. Any polynomial dominates any logarithm: n<sup>2</sup> + log(n) becomes n<sup>2</sup>.

For example, take the equation 4n<sup>2</sup> + n + 16 + log(n).

  • Omitting constants changes to n<sup>2</sup> + n + log(n).

  • Then, keeping the smallest factor leaves n<sup>2</sup> + log(n).

  • The polynomial dominates the logarithm, so it is removed: n<sup>2</sup>

Therefore, the equation reduced to Big-O notation is O(n<sup>2</sup>).

Sometimes when deducing Big-O, you may be working with logarithms. Here's a helpful chart for navigating logarithm properties:

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Alg_BigO_02.png" alt="logarithm cheat-sheet" style="width:400px;max-width:95%;"> </div>

Other Types of Big-O Comparisons

In the definition of Big-O notation, it was mentioned that a function f(n) is O(g(n)) where g(n) is another function or value. There are two additional ways to represent functions in Big-O notation that, though less commonly used, are still important.

Omega

While Big-O describes the upper bound of an algorithm's performance, Omega describes the lower bound of an algorithm's performance. Another way of saying it is:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">f(n) = &Omega;(g(n)) if f(n) grows no slower than g(n).</div><br> If you know both the Big-O and Omega performance times of an algorithm, you know that It can never run any better than a certain constraint, but it can also never run any worse than another constraint.

For example, we can say that a function f(n) is O(n<sup>2</sup>) and O(n) if it grows faster than both of them. This means that when deducing Big-O notations, picking the closest possible choice is much more informative.

Theta

If a function f(n) has bounds O(n) and O(n), it is said to be &Theta;(n);

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">f(n) = &Theta;(g(n)) if f(n) grows as fast as g(n). </div><br> If you can say a function is theta of a certain bound, then you know with a fairly high degree of confidence the exact growth rate of the algorithm.

For example, if f(n) is &Theta;(n<sup>3</sup>) and g(n) is &Theta;(n<sup>3</sup>), then f(n) = &Theta;(g(n)).

Practice

To understand how to evaluate algorithms in terms of Big-O notation, it will help to see some examples of common cases.

O(1)

An algorithm is said to be constant if the amount of time or memory it requires is independent of the size of the data set. A constant time algorithm is denoted in Big-O as O(1). An excellent example of this in real programming is accessing an array element:

Int [] array = { 9, 12, 7, 2, 8 }
function getIndex(int index) {
    return array[index];
}

In this example, the function getIndex takes O(1) time to execute as no matter how large array is; it will always take the same amount of time to return the index. The array could be 10 elements, or it could be 10,000 elements, and it will always take (generally) the same amount of time to complete the function.

O(n)

If an algorithm has linear performance, then the amount of time that it takes to complete, or the amount of memory that it uses, is directly proportional to the size of the data set.

An example of an algorithm that takes O(n) time to execute is an algorithm that attempts to find the smallest element in an array.

int [] array = { 8, 11, 3, 6, 2, 9 }

function findSmallest() {
    int smallest = array[0];
    for ( int i = 0; i &lt; array.length; i++) {
        if ( i &lt; smallest ) {
            smallest = i;
        }
    }
    return smallest;
}

The amount of time that findSmallest takes to perform relies on the size of array. If the array contained ten numbers, it would take twice as long as if the array contained only five numbers.

O(n<sup>2</sup>)

An algorithm that has a performance that is the square of the size of the data set has O(n<sup>2</sup>) performance.

Most commonly, exponential performance takes on the form of nested loops. Imagine wanting to print out a square of asterisks (*) on a computer screen where the size of the square is specified as n in the x and y direction. If you only did this using two loops and no multiplication, it might look like this:

function printSquare(int n) {
    for(int i = 0; i &lt; n; i++) {
        for(int j = 0; j &lt; n; j++) {
            print("*");
        }
        print("\n");
    }
}

If a function contained more nested loops, it's runtime performance would continue to increase exponentially to O(n<sup>3</sup>), O(n<sup>4</sup>), and so on.

O(log n)

Logarithmic performance is often associated with pseudo divide and conquer algorithms such as binary search. These algorithms are often similar to divide and conquer algorithms in that they divide the problem into smaller pieces, however algorithms like binary search discard the data that is not being looked for instead of operating on it.

Further Resources