COMPLEXITY
Execution Time as a Function of Problem Size


COMPLEXITY is a set of MATLAB programs which investigate the time complexity of a few simple calculations.

Time complexity can refer to the relationship between problem size n and execution time t. Algorithms may exhibit logarithmic, linear, quadratic, or exponential time complexity. A quadratic time complexity suggests that a formula such as t = a + b * n + c * n^2. However, there is no point in trying to be so precise, and the important feature here is the occurrence of n^2, whose growth rate will eventually characterize the function. Thus, we tend to simplify such a relationship by writing t=O(n^2), saying "t is of the order of the square of n". A more subtle complexity might have the form t = O(n * log(n) ), which is a form that actually occurs fairly often.

For short, simple algorithms, it is possible to work out the time complexity as a formula. However, practical algorithms often have complications that make it tedious to seek such a formula. Moreover, the computer implementation and the memory access patterns may also have a pronounced effect on the behavior of a program, particularly when the problem size is large. Thus, whether we can predict or estimate the time complexity of an algorithm, we can experimentally measure it on a range of problem sizes and draw our own conclusions.

In this directory, we consider a few simple algorithms, using them to solve problems of increasing size, measuring the elapsed time, and making plots.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

COMPLEXITY is available in a MATLAB version.

Related Data and Programs:

LINPACK_BENCH, a MATLAB program which measures the time taken by LINPACK to solve a particular linear system.

MXM, a MATLAB program which sets up a matrix multiplication problem A=B*C of arbitrary size, and compares the time required for IJK, IKJ, JIK, JKI, KIJ and KJI orderings of the loops.

NAS, a MATLAB program which runs the NASA kernel benchmark.

TIC_TOC, MATLAB programs which demonstrate some features of MATLAB's tic and toc functions for wallclock timing.

Source Code:

BUBBLESORT_COMPLEXITY considers the time complexity of the bubblesort algorithm.

ELIMINATION_COMPLEXITY considers the time complexity of Gauss elimination.

HEAPSORT_COMPLEXITY considers the time complexity of the heapsort algorithm.

You can go up one level to the MATLAB source codes.


Last revised on 23 December 2012.