A Simple Guide to Time Complexity

Code Execution Counts

Given a piece of code, its total execution count can be represented by T(n), where n is the size or amount of input data. T(n) is the total execution count of a piece of code when the input size is n.

Take the following two code snippets as examples:

int func1(void)
{
	printf("Hello World!\n");
	return 0;
}

The total execution count of this code is T(n)=2 (the two statements each execute once)

int func2(int n)
{
	for(int i = 0; i < n; i++)
	{
		printf("Hello World!\n");
	}
	return 0;
}

The total execution count of this code is T(n)=3n+3 (int i = 0 executes 1 time, i<n executes n+1 times, i++ executes n times, printf executes n times, and return executes 1 time)

In practice, however, statements are generally not counted one by one; an estimate is used instead.

Time Complexity

A simplified estimate of the code’s execution count is its time complexity.

How to Derive Time Complexity from Code Execution Count

The simplified relationship between code execution count T and time complexity O is as follows:

Code execution count T	Time complexity O
Constant	O(1)
Constant × n + constant	O(n)
Constant × n^2 + constant × n + constant	O(n^2)
Constant × n^a + constant × n^(a-1) …	O(n^a)

For example, if T(n)=constant, the time complexity can be estimated as 1.

For a polynomial, for example, retain only the highest-order term and ignore its coefficient, because the lower-order terms grow much more slowly than the highest-order term.

Time Complexity of Common Code Patterns

Standard Cases

(1) No loops

Time complexity: O(1)

(2) A single loop

Time complexity: O(n)

(3) Two nested loops

Time complexity: O(n^2)

(4) Multiple nested loops

Time complexity: O(n^a) where a is the number of loop levels

(5) Multiple loops

Time complexity: O(n^a) where a is the number of levels in the most deeply nested loop

(6) if..else.. with nested loops

Use the branch with the highest time complexity.

Special Cases

(1) i grows proportionally

void func(int n)
{
	for(int i = 1; i < n; i *= 2)
	{
		printf("Hello World!\n");
	}
}

Total code execution count: T(n)=3log2(n)+2 Time complexity: O(log(n))

Significance of Time Complexity

With different time complexities, code execution time increases differently as the amount of input data grows.

For example, with O(1), the code’s execution time remains unchanged no matter how much the input data grows. The execution time of O(n) is proportional to the amount of input data. If the time complexity is too high, such as O(2^n), the code can still run with a small amount of data, but once the amount of data grows, the execution time will increase geometrically.

The code execution times are summarized below:

Name	Time complexity
Constant time	O(1)
Logarithmic time	O(log n)
Linear time	O(n)
Linearithmic time	O(nlog n)
Quadratic time	O(n^2)
Cubic time	O(n^3)
Exponential time	O(2^n)