Big-O Notation

Hi everyone, here is my second post on computer science. Contrary to what I said before (sorry!), this will be about big-O notation, a very important concept in computer science.

Big-O notation is a system used to analyze how fast a program runs or how much memory it takes up. We'll focus on time for now, but it can similarly be applied to other things.

The "big-O" of the run time of a program is usually denoted as $O(f(n))$, where $f(n)$ is some function of $n$. For example, if a program runs in big-O of $n$ squared, we would write that as $O(n^2)$.

Usually, $n$ denotes the amount of input to the program. Then, the function is the number of operations the computer executes to go through the program. The run time is analyzed as $n$ approaches infinity, so if the number of operations is the sum of multiple terms, only the one that grows the fastest is considered. Also, any coefficients are ignored.

For example, here are some possible big-O categories from fastest to slowest, along with some programs that might fall under each category:

• $O(1)$: This is the best big-O category. It means that no matter how much input there is, the program always takes the same amount of time. Very few programs fit this definition. One example is a program that takes in a list and returns the first element of the list.

  • $O(\log(n))$: This is a pretty nice big-O category. It grows much slower than $O(n)$. For example, binary search on a sorted list takes $O(\log(n))$ time. Note that the base of the logarithm is not included, since all logarithms differ only by a factor of a constant.

  • $O(n)$: This big-O category usually results when a program iterates over data one or more times. For example, a program to find the maximum value in a list usually falls under this category, as it loops over the list once keeping track of the maximum so far.

  • $O(n\log(n))$: Included because often-used sorting algorithms, such as mergesort and quicksort, fall under this category.

  • $O(n^2)$: This category happens when a program has a loop within a loop.

  • $O(a^n)$: This is a very slow big-O category. Usually, a program in this category has $n$ values that each can be any of $a$ values.

  • $O(n!)$: This is one of the worst big-O categories. Usually, a program in this category works with all permutations of a list.

There are many more possible categories, including products of the above, but the above are very common.

When solving computer science problems, big-O notation can be a valuable tool to figure out whether an approach is feasible or not. Here is an example of using it:

Write a program that prints all permutations of the first $n$ positive integers that are in strictly increasing order.

Okay, perhaps the program is really easy to write, since the only permutation is obvious. However, let us consider another approach: going through every permutation and examining whether the elements are in increasing order. This would run in $O(n!)$ time, since there are $n!$ permutations. It takes a constant number of operations to check each permutation, and the constant is dropped. This is infeasible, as $n!$ grows much too fast. Even $15!$ would take a nontrivial amount of time.

Here is another problem:

Pseudocode:

function sum(list):
    sum = 0
    for each element in list:
        current = element
        add current to sum
    sum = sum*1
    return sum

Find the big-O category for this program.

We can quickly see that this program finds the sum of the elements in a list. It may not be the most efficient, but it works.

First, it sets sum to 0, which takes one operation. Then, it iterates over the list, performing two operations each time. This takes $n$ time. Then, it performs two more operations.

Overall, the total time is $1+n\times 2+2=2n+3$. The fastest growing term is $n$, and we ignore the coefficient of 2, so the big-O category is $O(n)$.

One last note: while the big-O category can help in analyzing algorithms, it isn't the only thing to consider. Programs within the same category can be significantly faster or slower than another. Also, don't forget to consider memory usage as well as time.

Problems:

1. Think about big-O notation and try to categorize some programs you write.

2. I'll put up some problems asking for the big-O time category of some programs soon.

Thanks for reading! I hope you use big-O notation to analyze algorithms in the future.