Algorithm Runtimes and Runtime Analysis

Algorithm efficiency is often described in terms of the runtime of the algorithm. It is often important for algorithms to run as fast possible so as to minimize the amount time the computer spends working on any one task. Because of this need to efficient algorithms, many computer scientists have spent a great deal of time devising different ways means of completeing the same operation, but with different runtimes.

A classic example of a problem that has many different implementations, and many different runtimes, is the problem of sorting. To sort an array of integers, you can choose to use the selection sort algorithm, the insertion sort algorithm, bubble sort, merge sort, quick sort, or a variety of other types of sorts. Why are there so many sorting algorthms though? Its because many of them have different runtimes. For example, selection sort, insertion sort, and bubble sort all run in O(n² ) time (more on what this notation means later), while merge sort and quick sort run in O(nlg(n)) time.

It is important to understand the different runtime complexity classes for algorithms, and be able to determine the runtime of a given algorithm.

Big-O Notation

Typically, algorithm run times are expressed in “Big-O” notation (this is the notation used above). In Big-O notation, the runtime of the algorithm is expressed as a mathenatical function in terms the input size, n. The faster the mathematical function grows, the larger the runtime of the algorithm, and, often, the less desirable the algorithm is. Below are a few examples of Big-O notation:

O(c) - constant run time; The algorithm’s run time does not change regardless of the input size

O(n) - linear run time; The algorithm’s runtime grows linearly with the input size. An input that is 10x larger than another input will take 10x as long to run.

O(n² ) - quadratic run time; the algorithm’s runtime grows quadratically with the input size. An input that is 10x large than another input will take 100x as long to run.

O(lg(n)) - logarithmic run time; The algorithm’s runtime grows with the lg of the input size.

O(nlg(n)) - polylogarithmic run time; The algorithm’s runtime grows with the polylogarithm of the input size

There are, of course, other possible run times, but the above four are the most common ones will you see.

Related Runtime Notation

We call the above runtime evaluation syntax, Big-O notation. This is not technically correct. In addition to Big-O notation, there is also, Big-\(\Theta\) notation, as well as Big-\(\Omega\) notation. In a technical sense, an algorithm’s Big-O run time constitutes an upper bound on the run time of the algorithm, Big-\(\Omega\) run time constitutes a lower bound on the run time, and Big-\(\Theta\) runtime constitutes a tight bound on the run time.

In other words, any function larger than the true algorithmic run time can be said to be Big-O and any function smaller than true run time could be said to be Big-\(\Omega\) . Traditionally, when we talk about algorithmic runtimes, we are refering to the tightly bounded Big-\(\Theta\) runtime.

Indices and tables

• Index
• Module Index
• Search Page