complexity_test

complexity_test, 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_test 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:

• complexity_test.m, calls all the tests.
• complexity_test.sh, runs all the tests.
• complexity_test.txt, the output file.

BUBBLESORT_COMPLEXITY considers the time complexity of the bubblesort algorithm.

• bubblesort_complexity.m, the source code.
• bubblesort_1to200.png, plots the time require for problem sizes N = 1, 2, 3, ..., 200.
• bubblesort_powersoftwo.png, plots the time require for problem sizes N = 1, 2, 4, 8, 16, ..., 2^12.

ELIMINATION_COMPLEXITY considers the time complexity of Gauss elimination.

• elimination_complexity.m, the source code.
• elimination_1to200.png, plots the time require for problem sizes N = 1, 2, 3, ..., 200.

HEAPSORT_COMPLEXITY considers the time complexity of the heapsort algorithm.

• heapsort_complexity.m, the source code.
• heapsort_1to200.png, plots the time require for problem sizes N = 1, 2, 3, ..., 200.
• heapsort_powersoftwo.png, plots the time require for problem sizes N = 1, 2, 4, 8, 16, ..., 2^12.