Big-O Notation and Algorithm Analysis

Often in computer science, algorithms need to be compared for efficiency. It is hard to say if an algorithm is faster than another in a conventional sense. Insertion sort is usually much slower than quicksort, but when the input size is small, insertion sort tends to outperform quicksort. Also, even for very large sets of data, insertion sort sometimes (but rarely) outperforms quicksort.

To smooth out these complications, computer scientists, don't compare the running times of algorithms, but how the running time grows as the size of the data sets grow. To do this, big-O notation is used, which roughly approximates an algorithm's running time growth using a simplified mathematical function. For example, the value of $n^2$ quadruples when $n$ doubles, so an algorithm that is $O(n^2)$, such as bubble sort, will quadruple its running time if the array to be sorted doubles in size.

Also, for certain algorithms, luck also dictates how fast the algorithm runs, so best-case, worst-case, and average-case scenarios are usually assessed. Insertion sort is a great example of this. Normally, insertion sort is $O(n^2)$. However, when given a sorted list, an insertion sort algorithm will only iterate through the list, never swapping any elements, taking $O(n)$ time.

When determining the big-O of an algorithm, the true running time function is simplified because not all its parts contribute to how the function grows. For example multiplication by a constant isn't allowed in big-O, and neither is most addition. Something like $O(4n^2+2n+10)$ would simplify to $O(n^2)$. Below is a summary of common big-O running times, sorted by growth. $n$ is the size of the data set and $k$ is some constant.

Ideally, running time shouldn't be more than polynomial, but it really depends on the problem. In general, you should worry about writing a working program before worrying about optimizing it. Also, when optimizing, try to find the lines of code that spend the most time running and try to optimize those. For example, in the code below, focus on optimizing the set of nested for loops, not the while loop. If you could without breaking the program, remove one of the for loops to reduce the running time from $O(n^3)$ to $O(n^2)$.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // do stuff
        }
    }
}

int n;
while (x < n) {
    // do some other stuff
    x++;
}

Most importantly, if you know $n$ will never exceed some small value (such as 40), don't even bother optimizing. If you want to analyze whether a program runs within the specified time limits, keep in mind that a few million operations can be done per second. So if an algorithm was $O(n^2)$, the maximum possible $n$ would be around 5000 which gives 25 million operations in a second.

By first checking whether you solution would even run in time, you can save yourself the time of coding an incorrect solution. Besides checking runtime you should also take time to check the validity of a solution (i.e. it gives the right answers) before immediately jumping into coding it.