Have you noticed how some programs run faster than others? Or wondered why one process requires more memory than another? These questions connect to the concepts of time and memory complexity in algorithms. In this article, you'll dive into these aspects of algorithm analysis and see their influence on program performance.
Understanding Time Complexity
Time complexity provides insight into how an algorithm's execution time evolves as the size of the input increases.
The cornerstone of this concept lies in estimating the algorithm's efficiency. Time complexity can help us compare different algorithms and select the most effective one for each problem.
Take, for example, the task of searching. Assume you have a list of numbers, and you want to find a specific one within that list.
The conventional way to do this is to start at the beginning of the list and scan each number one by one until you find the number you're searching for.
The time it takes to find the number changes according to the list's size. Thus, the performance of an algorithm scales directly in proportion to the input size. We can briefly describe this kind of change with "algorithm scales linearly" and refer to this algorithm as a linear search.
For instance, if a list has 5 items, you might need up to 5 comparisons. But what happens if a list contains 5,000 items? You might need up to 5,000 comparisons in the worst-case scenario. The worst-case for linear search refers to the situation where your specific number happens to be the last one on your list.
In the picture below, blue numbers represent the amount of iterations through an array.
If you have 5 items in the array, you should perform 5 iterations for each item. If you have n items in the array, you should iterate n times.
Of course, your specific item can be anywhere in the list. However, you should always bear in mind that it could also be the last one too.
Understanding Space Complexity
Space complexity deals with the amount of memory or space an algorithm needs to solve a problem. It helps us grasp how the memory usage grows as the input size increases.
Space complexity becomes a concern when an algorithm manipulates large amounts of data. Excessive memory usage can lead to slower performance or even failure due to out of memory errors, such as a Stack Overflow Exception.This error typically occurs when a recursive method forms a deep call stack.
Consider an algorithm that computes the factorial of a number. Below is a simplified implementation of a function that calculates the factorial of an input number:
function getFactorial(n) {
if (n == 0) {
return 1
} else {
return n * factorial(n - 1)
}
}
function main() {
print(getFactorial(10))
}In this example, the space complexity is O(n). Let's examine this resolution closer.
The number of recursive calls that the
factorialfunction makes is equal to the value of the input datan.Each recursive call to the
factorialfunction adds a level to the call stack.Each level of the call stack requires a constant amount of space needed for things like the return address to the function.
As a result, the maximum depth of the stack depends directly on n. Hence, we need n amount of space to compute the factorial of n. The code above calculates the factorial of 10, indicating a maximum stack depth of 10.
Imagine your project includes an implementation of the factorial calculation, as demonstrated above. As long as you compute factorials of numbers like 10, 30, or 100, there's no need to worry about memory size.
But what happens if you need to calculate a factorial of 1 million, or 100 million? Can your computer handle this task?
We will address instances of huge input size further down.
The previous example focused on the memory needed for stack depth. Furthermore, memory is also required for new data structures created while solving a problem.
Below is a code snippet used for creating a multiplication table for a predefined array.
function getMultiplicationTable(numbers) {
table = []
for (i=0; i < numbers.size; i++)
row = []
for (j = 0; j < numbers.size; j++)
row.add(numbers[i] * numbers[j])
table.add(row)
return table
}
function main() {
print(getMultiplicationTable([1,2,4,5])
}We create a row for every single number for the table. Each row multiplies with each number and then adds it to the table. So, as the number of inputs increases, so does the number of rows and numbers in each row. The question is how exactly does it increase? The answer is quadratically.
To illustrate, recall how the multiplication table appears:
for 3 items, it has 9 elements
5 items - 25 elements
10 items - 100 elements, and so on.
In the next sections, we'll learn how to express time and memory complexity using specific notation.
Big O notation
The previous sections introduced time and space complexity to help grasp the ideas better. Now, we can discuss how the community chose to standardize these terms and how to compare different algorithms' complexities.
The community uses the Big O notation. It helps to describe the upper limit of an algorithm's time or space complexity.
In Big O notation, the term n represents the input size. As we've already discussed, depending on the input size, an algorithm's execution time or space may vary.
The table below outlines some common Big O notations alongside their meanings. The notations are listed in ascending order based on execution time.
Big O | Type of time/space complexity | The algorithm's runtime or memory usage: |
|---|---|---|
O(1) | Constant | remains constant, regardless of the input size. |
O(log n) | Logarithmic | increases logarithmically with the input size. |
O(n) | Linear | increases linearly with the input size. |
O(n^2) | Quadratic | increases quadratically with the input size. |
O(2^n) | Exponential | increases exponentially with the input size. |
Simplifying complexity
Complexity is simplified in order to gain a high-level understanding of an algorithm's efficiency. This simplification allows for easier comparison between different algorithms and the selection of the most efficient one. The most important aspect is focusing on the growth rate. We are primarily interested in how an algorithm's running time changes as the input size blooms. The exact running time or the specific number of operations is less vital than the rate of change.
Imagine you're choosing the best algorithm to solve a sorting problem. Let's also define that each iteration costs 1 millisecond. You have two options:
The Bubble sort with time complexity
O(n^2).The Quick sort with
O(n*log n).
Take a look at the table below to see approximate time results for each approach. Here, we're considering two scenarios with 10 and 2000 elements:
Number of elements | Bubble sort | Quick sort |
10 | ~100 milliseconds | ~33 milliseconds |
2000 | ~1 hour | ~22 seconds |
As you can see, when we increase the number of elements by around 200 times, the difference in results becomes dramatic. For 10 items, the Bubble sort approach can solve the problem in approximately 100 milliseconds, while the Quick sort can do so in roughly 33 milliseconds. It doesn't seem like a significant difference, right?
However, to sort 2000 items, the Bubble sort approach would take about 1 hour, while the Quick sort method would only take about 22 seconds. That is indeed a massive difference!
As you can see, understanding the growth rate and how it impacts the performance of an algorithm is crucial when trying to optimize efficiency.
Now let's see how we can simplify a complexity expression such as 3n^2 + 2n + 1.
To do this, we should focus on the dominant component, the component that grows the fastest as the input size increases. Let's simplify the given complexity expression step-by-step:
First, separate the overall complexity into components. Here we have three components:
3n^2,2n, and1.Then determine the complexity of each component. The first component,
3n^2, is quadratic multiplied by a coefficient. The second component2nis linear, also multiplied by a coefficient. The third one is a constant.Next, determine which component is dominant. According to the table above, the first component (with quadratic complexity), dominates over the other components. Therefore, we can ignore the other components.
Finally, examine the dominant component, which is
3n^2. As the coefficient becomes less significant asngrows, you can remove it. As a result, we have simplified the complexity toO(n^2), which is quadratic complexity.
As you can see, simplifying to the dominant component helps us to focus on making better decisions when choosing an efficient algorithm.
Complexity cases
When discussing the linear search algorithm, we introduced the concept of a worst-case scenario. This pertains to the circumstance whereby your specific item is the last one in the dataset. You would then need to search through all other items before finding the one you need. Below, you'll find two reasons why it's important to focus on the worst-case scenario for both time and space complexities:
Guaranteed performance: The worst-case scenario describes an upper bound on the algorithm's runtime. Regardless of the input provided, the algorithm's performance will never be worse than this scenario.
Consistency: Worst-case analysis does not rely on a specific type of input data. Therefore, it allows for the effective comparison of algorithm performance, regardless of specific use cases or datasets.
However, focusing solely on the worst-case scenario isn't always the best strategy. Sometimes, considering the average-case or best-case scenarios may provide valuable insights, especially if the worst-case is unlikely or if the average-case is significantly better than the worst-case.
For instance, consider the Quick sort algorithm. On one hand, its worst-case complexity is O(n^2). On the other hand, its average-case complexity is O(n log n), which is much better. As a result, Quick sort is, on average, more efficient than other sorting algorithms.
Analyzing Algorithm Efficiency
When analyzing an algorithm, we should consider its time and space complexity. The aim is to balance minimizing the execution time and optimizing memory usage. Depending on the specific requirements of the problem, we may need to prioritize one over the other.
You can analyze algorithm efficiency by following these steps:
Determine the time complexity. To do this, you can count the number of basic operations, considering the input size.
Using
Big Onotation, identify the dominant component to determine the overall time complexity.Repeat the above steps for determining space complexity.
Define if this complexity fits the problem you should solve.
Sometimes, complexities like Quadratic or Exponential could be converted to better ones using another approach to solving a problem. Imagine solving a problem with a cycle inside another with Quadratic total complexity. Depending on task-specific details or input, you should check if converting the input data to another data structure is possible. Maybe another data structure allows us to provide a solution with one cycle.
Anyway, it all relates to a problem details, and sometimes there is no other way to decrease complexity. For example, the Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph. It has a time complexity O(n^3) for all cases.
Conclusion
In this topic, you learned the fundamental concepts of time and memory complexity to analyze algorithm efficiency.
Here are the key points to remember:
Time complexity helps us understand the execution time of an algorithm.
Space complexity defines the memory usage that could be required during the execution.
Big O notation explains the upper bound of an algorithm's complexity.
You can simplify complexity by focusing on the dominant component.
It is essential to take into account the worst-case of algorithm execution for the majority of problems.
Some problems' details can allow you to decrease the solution complexity, and others cannot change the complexity.
By analyzing an algorithm's time and space complexity, we can make rational decisions about its efficiency. It leads to designing efficient solutions for each specific problem. Considering both complexities, we keep the balance between performance and memory usage.