Introduction
The time complexity of a function (or algorithm) can be seen as the relative time the function takes to process data of different sizes.
Time complexity is sometimes referred to as simply “complexity”, or “algorithmic complexity” or “asymptotic complexity”. We might measure the time complexity of a function with respect to best case, the average case or more likely and more generally the worst case.
Note: We generally talk about the time complexity of a function in terms of its worst case, however it’s possible we might declare the best or average case but we should therefore explicitly state that this time complexity is best or average case when using it, otherwise worst case is assumed.
As we’ll see, and you probably worked out from the title of this post, we have notation for this called Big O.
When I say “relative time” we’re not talking about the actual performance characteristics of a function as this may depend on the language used as well and the hardware running the function as well as the actual algorithm used. We’re not really interested directly in the actual time to run an algorithm or function but we’re more interested in how long it takes relative to the data or input growth. In other words whilst a function might take milliseconds for 100 items, what it we increase the data presented to the function to 10,000 items.
Disclaimer: This post is based upon a computer science view/usage of time complexity and Big O. It is not as rigorously written (or intended to be) as one would require far a mathematics based analysis and frankly it’s primarily based upon what I recall from my learning this stuff way back in the early nineties along with some refresher reading.
A simple example
Let’s look at something equivalent of the “Hello World” app. but for time complexity…
We have function which counts the number of elements in an array
func count(array: [Int]) -> Int {
var c = 0
for item in array {
c += 1
}
return c
}
The language is immaterial, although as I’m messing with Swift at the moment, that’s what I’m presenting here, but it’s so basic, hopefully it’s pretty obvious how this works.
Now let’s pretend I ran this code against an array of 100 items and it ran in 2ms then I ran the function again with 200 elements and measure the time to be 4ms. We can see that this might indicate a linear time complexity – in other words if we continually double the number of items we’d see a double of the time taken. Hence the time against size or growth of the data creates a linear graph (i.e. y = mx+c). Ofcourse we’d need to run a fair few more samples to prove this, but you hopefully get the idea.
But wait… I said at the start that we’re interested in relative time.
What we know about this simple function is that, as the array size grows the time complexity of the function grows in proportion to size, so now we need to figure out a way to represent this information.
Big O
Big O is used to represent our relative time using notation to represent time complexity. The notation starts with a capitalized (big) O (which represents order of) followed by parenthesis and within the parenthesis we have a constant or a formula using n usually, to represent the size of data.
In the count code (above), we’re having to iterate the array to count the number of items. Therefore, to find the length of the array we must iterate over N items, hence this function has a Big O of O(n). You’ll notice though that we have essentially three statements within this function, so let’s be a little more precise about how we calculate the Big O of this function.
func count(array: [Int]) -> Int {
var c = 0 // O(1)
for item in array { // O(n)
c += 1 // O(1)
}
return c // O(1)
}
The line where we assign the initial value to c has a constant time complexity (denoted as O(1)), in other words, this line and for that matter the incrementing of the c variable takes the same time whatever the size of input. However, the for loop must loop through each item in the array, hence has a time complexity of O(n), so we really end up with a total time complexity of
O(1) + O(n) + O(1) + O(1)
We can remove the constants as these become immaterial and are unaffected by the growth of the array, hence removing the O(1) we’re left with the O(n) time complexity.
There are a bunch of (if you like) standard time complexities you’ll see a lot, these are (in order of dominance)
O(1) = constant time O(log n) = logarithmic time O(n) = linear time O(n log n) = linear log time O(n^2) = quadratic time O(2^n) = exponential time O(n!) = factorial time
We ignore lower order terms when the algorithm is dominated by higher order terms, in other words O(n) dominates the O(log n) and hence a function that has both terms would have an overall term of O(n).
With regards our sample code, hopefully all languages will store the length of the array alongside the array data. Hence to access the length of an array we simply return this length variable and this happens in constant time O(1). Therefore, we can see that regardless of the size of the array the time to get the length variable will never change in such implementations. But if you’re used to C# think of the difference of using a List Count property against a Linq Count(). The first will return the stored count whereas the second would try to iterate the list giving quite different time complexities.
Working out the Big O of a function
We had a quick look at how to work out the time complexity of the count function, whereby we look at each line and apply the Big O notation to it, then we look for the dominant term and essentially this becomes our time complexity for the function.
Let’s now look at another function
func display() {
for x in 0..100 { // O(n^2)
for y in 0..100 {
print(x * y) // O(1)
}
}
}
This gives us O(n^2) + O(1), we can discard the constant and hence this function has a time complexity of O(n^2)
Time complexity as a range
It was mentioned earlier that we could calculate the time complexity for best, average or worst case. Whilst best and worst case give us a range to define the efficiency of our function and one might say that average gives us a useful value, we tend to concern ourselves most with the worst case. A simple example of this would be if we now change our count function to search an array for the first occurrence of a value, for example
func find(array: [Int], search: Int) -> Int{
var pos = 0
for item in array {
if item == search {
return pos
}
pos += 1
}
return -1
}
In the above code we can see that the only real difference from the previous count function is there’s a break from the O(n) loop when a match is found, therefore we can determine if the array’s first item was a match to our search parameter then this function would have a best case time complexity of O(1), on the other hand if the match was the last item we’d have a time complexity of O(n). Whilst we know that a best case gives us a constant time, we always need to look at the worst case. So, this function would still have a time complexity of O(n) as a worst case.
Why not just time our runs?
Earlier I mentioned some hypothetical timings for the count algorithm. Why don’t we just use those timings to represent our algorithm’s efficiency?
Well as you probably ascertained, we’re looking at have a machine independent measurement. Obviously if we’re comparing timings on a powerful development machine with lots of CPU power and memory our timings will not be indicative of the same algorithm on a low powered machine. Hence, we’re aiming to get a representation of a machine independent value.
As per the start of this post “The time complexity of a function (or algorithm) can be seen as the relative time the function takes to process data of different sizes.
“.
So, one must also remember that we’re measuring how an algorithm’s time complexity changes as data of different sizes are applied to it. But there’s a catch to this. What if we have function countA and it does the count process as implemented above but has a sleep, or some other constant time delay and compare it’s time complexity against the same function countB without this constant time delay, the Big O will essentially be the same, but obviously measured performance on the same machine will differ (potentially vastly differ).
For example, if our implementations looked like this
func countA(array: [Int]) -> Int {
var c = 0 // O(1)
for item in array { // O(n)
c += 1 // O(1)
}
return c // O(1)
}
func countB(array: [Int]) -> Int {
var c = 0 // O(1)
for item in 1..1000 { // O(1)
}
for item in array { // O(n)
c += 1 // O(1)
}
return c // O(1)
}
So, in countB we essentially have a constant time loop but it’s obvious from these two functions that countA will be more performant than countB but both will have the same O(n) time complexity.
So how do we deal with this difference?
In the response to that question, at this time, I’m not wholly certain. I need to research this further – but what’s obvious here is that the two algorithms will both be O(n) regarding the changes in the amount of data but not in a true comparison with one another as it’s obvious that countB will always be slower than countA.