Constant time complexity, as its name suggests, describes an operation that can be completed in a fixed amount of time. It means that the runtime, or memory requirement, of an algorithm does not depend on the size of its input. It is denoted by 1. Consider the example below, which calculates the average of two numbers.
We can see that adding two numbers \((C_0)\) requires one unit of time. The same is true for division \((C_1)\). Returning the result also requires one unit of time \((C_2)\). Therefore, \(T(n)=C_0+C_1+C_2\). We are only interested in the worst case, which means \(O(C_0)+O(C_1)+O(C_2)=O(1)+O(1)+O(1)=3\cdot O(1)=O(1)\). Recall that, by definition, \(f(n)=O(g(n))\) if \(f(n)\leq c_1\cdot g(n)\) for every \(n\) from some \(n_0\) onward. Therefore, \(g(n)=1\) and \(c_1=3\), so \(T(n)=O(1)\). We can clearly see that no matter what values we assign to \(a\) and \(b\), the runtime remains the same.
Introduction
During application development, we need to consider many aspects, such as security, modularity, and user experience. However, these factors can be strongly influenced by another metric. Performance. The speed of our software can affect user experience, modularity, and security alike. At first glance, this may seem far-fetched, so let us consider a few examples:User experience: If the application we develop is slow or unresponsive, it can negatively affect the user experience. Imagine if a Google search took two or three seconds, or if an image-editing application needed several minutes just to rotate an 8K image.
Modularity: Imagine that we have an API endpoint with a simple task: it returns products from a database according to the filters, or parameters, received in the request. Now imagine that this database is extremely large and contains billions of records. No one will want to use this endpoint if its response time is too high, which undermines its portability.
Security: This connection is not difficult to demonstrate, as runtime performance has compromised security on several occasions in the past. One such case occurred in an implementation of the TLS protocol (the full story of Lucky 13), where the problem was that errors were returned too quickly. Therefore, consistent runtime can sometimes be important.
The lesson we can draw is that it is useful to be able to provide a theoretical estimate of our algorithm's runtime.Runtime Analysis
How can we measure the runtime and memory usage of a program we have written? One fairly obvious approach is simply to measure it. We test it using a simple, small input, then increase the input size and examine the program under different configurations. However, this approach will not give us a complete picture of the algorithm's speed or memory usage. By examining only a finite number of values, we may not see the actual issue: the rate of growth. Furthermore, the actual runtime can be influenced by many factors beyond our control, such as system load, silicon lottery, cache...What interests us, therefore, is the rate at which our program's runtime and memory usage grow. First, we need to define the runtime function associated with our program, which we will denote by \(T(N)\). Here, \(N\) is the size of the input. Other factors may also affect the runtime function, such as whether the input is sorted, but we will disregard them for now; we will see an example later.
Consider the example below, in which we search for the maximum value in an array. We will focus only on the function; the surrounding boilerplate is not relevant. It is included only for demonstration.
import math
x = [10, 3, 20, 4, 1, 12, -3, 0]
def maximum(array):
maximum_value = -math.inf
for element in array:
if element > maximum_value:
maximum_value = element
return maximum_value
print(maximum(x))Let us examine what happens inside the function. On line 6, there is a value assignment that can be performed in one unit of time. Why exactly 1? Because assigning a value to a variable does not depend on the size of the input. Next, on line 7, we begin traversing the array, which visits every element in the array. We usually assume that the size of our input is \(N\), as mentioned earlier. Therefore, the time cost of the loop is \(N\). On line 8, we check whether the current element is greater than the largest element found so far. The time cost of the comparison is also 1, but we perform it \(N\) times. The next line contains another assignment with a cost of 1, which is also performed \(N\) times in the worst case. Finally, we return the value, which again has a cost of 1.
Overall, our runtime function is: $$T(N)=N+2$$
Growth Rate
Our runtime function appears simple and easy to read, but it can quickly become unwieldy for more complex algorithms. Moreover, we are only interested in how runtime grows, so many details can be omitted, as we will see. We can examine the growth rate from three perspectives, and \(O(\cdot)\) will be the notation used most often throughout the course:- Best case:
- Formally, \(f(n)=\omega(g(n))\) if \(c_1\cdot g(n)< f(n)\) for every \(n\) from some \(n_0\) onward. [little omega]
In other words, we can provide a function that, when multiplied by a constant, is STRICTLY smaller than our runtime function. - Formally, \(f(n)=\Omega(g(n))\) if \(c_1\cdot g(n)\leq f(n)\) for every \(n\) from some \(n_0\) onward. [big omega]
In other words, we can provide a function that, when multiplied by a constant, is smaller than our runtime function. In this case, equality is allowed.
- Formally, \(f(n)=\omega(g(n))\) if \(c_1\cdot g(n)< f(n)\) for every \(n\) from some \(n_0\) onward. [little omega]
- Average case:
- Formally, \(f(n)=\Theta(g(n))\) if \(c_1\cdot g(n)\leq f(n)\leq c_2\cdot g(n)\) for every \(n\) from some \(n_0\) onward. [theta]
In other words, we can bound our runtime function from below and above using two different constant multiples of the same function.
- Formally, \(f(n)=\Theta(g(n))\) if \(c_1\cdot g(n)\leq f(n)\leq c_2\cdot g(n)\) for every \(n\) from some \(n_0\) onward. [theta]
- Worst case:
- Formally, \(f(n)=o(g(n))\) if \(f(n) < c_1\cdot g(n)\) for every \(n\) from some \(n_0\) onward. [little o]
In other words, we can provide a function that, when multiplied by a constant, is STRICTLY greater than our runtime function. - Formally, \(f(n)=O(g(n))\) if \(f(n)\leq c_1\cdot g(n)\) for every \(n\) from some \(n_0\) onward. [big O]
In other words, we can provide a function that, when multiplied by a constant, is greater than our runtime function. In this case, equality is allowed.
- Formally, \(f(n)=o(g(n))\) if \(f(n) < c_1\cdot g(n)\) for every \(n\) from some \(n_0\) onward. [little o]
Below are several examples of \(\Omega,\Theta,\text{ and }O\) functions for the assumed runtime function \(T(n)=f(n)\).
Classes of Time Complexity
To make comparisons easier, we classify our algorithms into the following complexity classes: $$1 < \log{n} < \sqrt{n} < n < n \log{n} < n^2 < n^3 < \dots < 2^n < 3^n < n! < n^n$$ We will also examine them through a few practical examples.Constant Time Complexity
def avg(a, b):
sum_ = a + b
avg_ = sum_ / 2
return avg_
print(avg(3, 5))Linear Time Complexity
It is quite rare for an algorithm's runtime to be independent of the size of its input. This usually occurs only for isolated primitive operations. In contrast, linear time complexity means that runtime changes in direct proportion to the size of the input. It is denoted by \(n\). Consider the code below, which once again calculates an average, except that the input is an array of length \(n\), and the function returns the average of its elements.
First, we set the value of the sum_ variable to 0 \((C_0)\). This operation does not depend on the size of the input, so it can be completed in constant time. Next, we begin iterating over the array \((C_1)\), whose assumed length is \(n\). The body of the loop therefore executes \(n\) times. In this example, the number of iterations may depend on the body of the loop; we will see an example of this later. The body of our loop contains a single operation, which adds an element of the array to the sum_ variable. This requires one unit of time and is executed \(n\) times \((C_2)\). After that, we only retrieve the length of the array, which requires one unit of time, perform a division, which also requires one unit of time, and return the result, which requires one more unit of time. Therefore, \(C_3=1+1+1=3\).
Overall, our runtime function is: $$T(n)=2n+4,$$ but we are interested in its growth rate, which in Big-O notation is: $$2n+4 \leq c_1\cdot g(n), c_1=3, n=4, g(n)=n \rightarrow O(n)$$
First, we set the value of the sum_ variable to 0 \((C_0)\). This operation does not depend on the size of the input, so it can be completed in constant time. Next, we begin iterating over the array \((C_1)\), whose assumed length is \(n\). The body of the loop therefore executes \(n\) times. In this example, the number of iterations may depend on the body of the loop; we will see an example of this later. The body of our loop contains a single operation, which adds an element of the array to the sum_ variable. This requires one unit of time and is executed \(n\) times \((C_2)\). After that, we only retrieve the length of the array, which requires one unit of time, perform a division, which also requires one unit of time, and return the result, which requires one more unit of time. Therefore, \(C_3=1+1+1=3\).
Overall, our runtime function is: $$T(n)=2n+4,$$ but we are interested in its growth rate, which in Big-O notation is: $$2n+4 \leq c_1\cdot g(n), c_1=3, n=4, g(n)=n \rightarrow O(n)$$
x = [4, 10, 2, -100, 69, 42, 100, -25]
def avg(A):
sum_ = 0
for number in A:
sum_ += number
return sum_ / len(A)
print(avg(x))Logarithmic Time Complexity
When we refer to logarithms, we mean base-2 logarithms. At first glance, it may be difficult to imagine how this could relate to the runtime of any algorithm, but it becomes intuitive when we consider that our programs are built from \(if\dots else\dots\) branches. An \(if\) branch represents a binary decision that eliminates the other branch. If we can use such a decision to reduce the number of elements that must be examined, that number will decrease logarithmically. One example is binary search, which requires the input array in which we are searching to be sorted. The task is to return the index of the target element, or \(-1\) if the array does not contain it.
Let us examine the algorithm line by line.
Let us examine the algorithm line by line.
- Our parameters are the array (A) and the target value (value).
- On line 4, we initialize three values, which requires constant time \((C_0=3)\):
- low: points to the beginning of the array on the left
- mid: will point to the middle value of the array
- high: points to the last value of the array on the right
- On line 6, we begin our loop, which continues until the two boundary pointers meet. At first glance, it may not be obvious that this loop executes \(\log n\) times, so we will return to this point later. The comparison itself takes constant time.
- On line 7, we set the middle pointer so that it points to the middle of the array. This is calculated by taking an average and rounding it down. Rounding down is necessary so that the algorithm also works with arrays of odd length.
- On line 9, we check whether the middle value is the target value. If it is, we return its index and the algorithm is finished.
- If we are not that fortunate, we continue with line 12, where we check whether the target value is smaller than the middle value. If it is smaller, we do not need to search the right half of the array. Because the array is sorted, all values on the right would be greater.
high = mid - 1
From this point onward, we only search the left half of the array. Because the search area is halved in every iteration, the loop executes only \(\log n\) times in the worst case. - Line 14 is the same as the previous step, except that we discard the left half of the array and search the right half.
- Line 17 is executed only if the two boundary pointers meet, which means that the element was not found in the array.
x = [2, 5, 10, 15, 30, 40, 200, 1000]
def binary_search(A, value):
low, mid, high = 0, 0, len(A)-1
while low != high:
mid = (low + high)//2
if A[mid] == value:
return mid
if value < A[mid]:
high = mid - 1
else:
low = mid + 1
return -1
print(binary_search(x, 5))Quadratic Time Complexity
Quadratic, or square, time complexity is fairly easy to visualize by nesting two linear operations inside one another. Think of two nested \(for\) loops. It is denoted by \(n^2\). Vector multiplication is an example of a commonly used algorithm with this runtime. Consider the code below, which searches for one duplicate value in an array and returns the positions of its two occurrences.
- On line 4, we begin traversing the array, whose size is \(n\). This gives us a reference variable against which we can compare the other elements.
- On line 5, we begin traversing the array again so that we can compare our reference variable with the other elements of the array.
- We specify that the two values are considered equal only if they are located at different positions in the array and their values match.
- Finally, we return the two positions, or \(-1\) if the array contains no duplicate.
x = [3, 20, 4, -10, 42, 1, 22, 177013, 42, 10]
def duplicate(A):
for i in range(len(A)):
for j in range(len(A)):
if i != j and A[i] == A[j]:
return i, j
return -1, -1
print(duplicate(x))Combined Time Complexity
An algorithm's runtime is usually a combination of several primitive time-complexity classes. In practice, we rarely encounter simple cases. For example, consider what happens when we combine the algorithms used previously:
This algorithm has no particular practical purpose and is included only as a demonstration. It simply reuses the code fragments introduced earlier. What does the code do? It removes the single duplicate from the array, calculates the average, and returns the position of that average. We already know the growth rates of the functions it uses:
This algorithm has no particular practical purpose and is included only as a demonstration. It simply reuses the code fragments introduced earlier. What does the code do? It removes the single duplicate from the array, calculates the average, and returns the position of that average. We already know the growth rates of the functions it uses:
- avg: \(O(n)\)
- binary_search: \(O(\log{n})\)
- duplicate: \(O(n^2)\)
- del A[duplicate_indices[0]]: \(O(1)\)
x = [-20, -10, -3, 3, 8, 10, 18, 24, 42, 42]
def avg(A):
sum_ = 0
for number in A:
sum_ += number
return sum_ / len(A)
def binary_search(A, value):
low, mid, high = 0, 0, len(A)-1
while low != high:
mid = (low + high)//2
if A[mid] == value:
return mid
if value < A[mid]:
high = mid - 1
else:
low = mid + 1
return -1
def duplicate(A):
for i in range(len(A)):
for j in range(len(A)):
if i != j and A[i] == A[j]:
return i, j
return -1, -1
def combine(A):
duplicate_indices = duplicate(A)
del A[duplicate_indices[0]]
avg_ = avg(A)
position_of_avg_value = binary_search(A, avg_)
return position_of_avg_value
print(combine(x))Exercise 1.
Determine the growth rate (in Big O) of the following function!
Exercise 2.
Determine the time complexity of the following code segment!