Decoding the Complexity #1: An In-Depth Look at Asymptotic Analysis

Introduction

Understanding algorithm analysis is essential for creating and applying effective software. This process involves grasping not only how algorithms function but also how they perform under various conditions. This introduction will lay the foundation for a deeper understanding of Asymptotic Analysis, onboard!

Algorithms are systematic instructions that drive all computer operations, from simple calculations to complex data processing tasks. The analysis of an algorithm goes beyond understanding its logic; it involves assessing its efficiency and effectiveness (based on the input size).

Asymptotic analysis plays a vital role in understanding how algorithms perform as their input sizes grow larger and larger. This type of analysis is key to determining how much resources an algorithm will need, which is crucial for creating efficient algorithms that work well. In this article, we’ll explore how asymptotic analysis helps us tell apart algorithms that might look good on paper but don’t perform well in practice from those that can actually handle real-world tasks effectively.

Mathematical Foundations

Understanding the mathematical foundations of asymptotic analysis is crucial for effectively analyzing algorithms. Let’s break down some key concepts with simple explanations and examples.

Limits and Approximations

The concept of limits helps us understand how an algorithm/function behaves as we inject large inputs.

Think of a limit as what a function value is getting closer to as you plug in larger and larger numbers. For example, if you keep increasing n in the function f(n) = 1/n² the number will continue to decrease:

To digest this piece of information, we will consider a real-world scenario where you are distributing a fixed amount of water (say 1 litre) into an increasing number of buckets. If you start with 1 bucket, each bucket gets 1 litre. With 10 buckets, each gets 0.1 litres. With 100 buckets, each gets 0.01 litres, and so on. As the number of buckets n increases, the amount of water each bucket receives​ gets closer and closer to 0. To formalize this example mathematically we introduced the notation below:

Growth Rates

Growth rates are tools for software engineers to benchmark different algorithms which aim to solve the same problem. There are various categories of them, so let’s enumerate them from best to worst:

• Constant Growth (O(1)): The performance stays the same regardless of the input size. Imagine that you want to peak the first item in the list. Even if the array size is a million long, it will take the same amount of time to return the first item of a list.

• Logarithmic Growth (logn): Solves problems by repeatedly dividing the input size. Such a problem can be finding a name in a phone book. You open it in the middle to check the letter and repeat this process until you find the phone number of the given name. A more detailed description of this will follow later in the article.

• Linear Growth (O(n)): The performance increases directly in proportion to the input size. For example, taking a cab ride where you are charged proportionally to n kilometres.

• Quadratic Growth (O(n²)): The performance increases with the square of the input size. For instance, a teacher compares each student ID with each person in a class.

Exponential Growth (O(2^n)): The performance doubles with each additional input. A good real-life example can be the spread of the virus COVID-19.

Factorial Growth (O(n!)):​ The time grows factorially with the input size, making it impractical for even moderately sized inputs. The most common factorial problem is the travelling salesman problem via brute force enumeration of all possible routes.

Important: As the input of an algorithm grows, we focus on the higher order term because it will grow faster and dominate the rest of them. By focusing on this term, we can simplify our analysis and make it easier to compare different algorithms. For practical example read the plyunomial functions below.

Cheatsheet: O(1) < O(α(n)) < O(log n) < O(n log n) = O(n log n) < O(n) < O(n²) < O(n³) < O(2^n) < O(n!)

Polynomial, Exponential, and Logarithmic Functions

The most common functions we explore are polynomial, exponential, and logarithmic ones.

Polynomial functions

Polynomial functions have the following form:

where aₖ, aₖ₋₁, …, a₀ are the constants and k is a non-negative integer. If we have some actual numbers (k=3, a = [4,3,2,1]) the function will convert into:

As you notice, the function proliferates due to the 4n³ term, which dominates the growth rate for larger values of n. This visualization helps to understand the polynomial nature and the steep increase in the function’s value with increasing n and why we simplify our comparisons with the most dominant term of the equation.

Logarithmic Functions

Logarithms answer a simple question “To what power must a base be raised, to produce a given number n?”. This quote mathematician formalized it as:

• logₐn which means logarith of n with base of a.
• Also mathematically we can picture it as aˣ = n <=> logₐn = x.

To picture its functionality let’s pose the question “To what power must 2 be raised, to produce 8?”.

Formalized: 2ˣ = 8 <=> log₂​8 = x.

Let's work our way to the solution by increasing our n:

It’s evident that n = 3. However, the key takeaway is that as n increases, the x value increases slowly, which makes logarithmic complexity attractive. Another thing that you should pay attention to is that in computer science, we deal especially with binary data and algorithms. Hence, we are interested more in base 2. Therefore, your equation will always have the format of log₂​n = x.

Exponential functions

In an exponential function, the input size n appears as the exponent. This leads to extremely fast growth rates. For example, if a = 2, the function f(n) = 2ⁿ doubles with each increment of n.

As shown, the function’s values increase very rapidly as n grows. This rapid growth is a hallmark of exponential functions, and thus we should improve — if possible — the complexity of such an algorithm.

Fundamentals of Asymptotic Analysis

Definition of Asymptotic Analysis

Asymptotic analysis is a fundamental tool in computer science, used to describe the behavior of algorithms as the input size increases substantially. This procedure does not provide a precise estimation of the time required by an algorithm, but rather an abstract approximation.

The role of asymptotic analysis in assessing algorithm efficiency is pivotal. It serves several key functions:

1. Comparative Analysis: It enables the comparison of different algorithms based on their time or space complexity. This is particularly useful when deciding which algorithm to use for a specific application.
2. Performance Prediction: Asymptotic analysis helps in predicting the behavior of an algorithm under different scenarios, especially with large datasets. This predictive power is crucial in an era where data is continuously growing in size and complexity.
3. Algorithm Design: Understanding the asymptotic behaviour of algorithms guides developers and researchers in designing more efficient algorithms. It encourages a focus on scalability and efficiency from the outset of the algorithm design process.
4. Benchmarking: It provides a standard way of talking about and benchmarking algorithm performance, which is essential in both academic research and practical applications.

Connect real life with the Asymptotic Analysis

Let’s try to simplify it by utilizing an example. Imagine someone needs to transport the groceries from point A to B. We assume that the groceries weigh N kg. We’ve examined our options and have concluded that there are three ways to move them by foot, by car, and via a drone.

The slowest method would be walking. It would be fair to estimate that as the weight of groceries increases the more time we need to transport them. So if the first estimate is about an hour, we can say that it will grow exponentially.

• For N kilograms, T = 2^(N/N — 1) = 2⁰ = 1 hour.
• For 2N kilograms, T = 2^(2N/N — 1) = 2¹ = 2 hours.
• For 4N kilograms, T = 2^(4N/N — 1) = 2² = 4 hours.
• and so on!

This pattern illustrates how even a small increase in weight can significantly affect the time needed for transportation. Hence, we can assume walking with groceries long distances wouldn’t benefit us.

As mentioned, using a car for transporting groceries is another option. A rough estimate for transportation time by car is around 30 minutes. However, it’s reasonable to assume that this time will increase linearly with the weight of the groceries. Heavier loads can lead to lower fuel efficiency, thus requiring more frequent stops at gas stations. Additionally, increased weight might also mean less agility in navigating traffic, potentially leading to longer waits at traffic lights.

• For N kilograms, T = 1 x 30 minutes = 30 minutes.
• For 2N kilograms, T = 2 x 30 minutes = 1 hour.
• For 3N kilograms, T =3 x 30 minutes = 1 hour and 30 minutes.
• For 4N kilograms, T =4 x 30 minutes = 2 hours.
• …

Straight out of the box, we can classify the car as a better option than walking, which is proven in our minds by our life experiences.

That leads us to the examination of the drones. The manufacturer of drones has guaranteed us that weight is not a problem. Hence, the person needs to load the drones and they will fly from point A to B. There is no traffic in the air which implies that the drones will perform the same regardless of the distance equal to 15 minutes.

• For N kilograms, T = 15 minutes.
• For 2N kilograms, T = 15 minutes.
• For 3N kilograms, T = 15 minutes.
• For 4N kilograms, T = 15 minutes.

Eureka! This preliminary assessment of the three transportation methods sets the stage for a fascinating comparison. It becomes apparent that drones are the fastest, followed by cars, and then walking. In the realm of algorithm analysis, we use notations like Big O (O), Big Theta (Θ), and Big Omega (Ω) to represent an algorithm’s performance. These Greek symbols, reflecting the influence of ancient Greek mathematics, provide a way to classify algorithms based on how their run time or memory requirements grow as the size of the input increases.

Big O notation

Among all the notations, Big O is the most popular, and there is a good reason for this. Big O notation indicates how our algorithm performs at its limits as the input size grows toward infinity. It is useful for comparing algorithms, especially to understand their behaviour with large inputs. This notation examines the “worst-case” scenario.

The significance of Big O lies in its independence from the programming language, hardware requirements, and minor code optimizations. It focuses on the growth rate of the major factors that will result in increased resource usage. For instance, an algorithm with a time complexity of O(n) will take time proportional to the input size, whereas one with O(n²) will take time proportional to the square of the input size. This simplification facilitates easier comparison and understanding of different algorithms.

Mathematical definition

Mathematically, Big O notation is used to describe the upper bound of a function up to a constant factor. A function f(n) is O(g(n)) where it exist positive constants c and n₀ such as:

f(n) ≤ c * g(n), for every n > n₀

Bear with me it will make sense in a few lines. Suppose you’re at a racetrack, watching two cars prepare for a race — our function f(n) = 4n² + 16n + 2 is like a fast car, but we’re looking for one that can speed away even faster. So, we line up another vehicle, g(n) = n⁴, known for its incredible acceleration. As we watch them race, you’ll notice how quickly g(n) pulls ahead, leaving f(n) steadily behind. A visualization of this narrative can be the following:

Q: Does this candidate satisfy our question? Does f(n) is O(n⁴)?

To address this question, we should refer to the rule that indicates when a function f(n) is O(g(n)). Our objective is to identify constants c and n₀ that fulfil the criterion: f(n) ≤ c * g(n), for every n > n₀.

There are several approaches to this question. A visual inspection can provide us with the solution in a simple case, such as the one we examine. By decomposing the graph, we can confirm that beyond the point (3.07, 88.81), g(n) surpasses f(n) in growth. Consequently, we can choose n₀ = 3.07 and c = 1 to satisfy the criterion, as f(n) ≤ 1* n⁴ for all n > 3.07.

Similarly, we could construct a trial-error approach by evaluating both functions from n = 1 to n = 6:

The comparison of the values of f(n) and g(n) for integers from 1 to 6, illustrates how g(n) grows more rapidly than f(n) as n increases over 3.

Unfortunately, there is a catch. Both of the previous solutions will not help us with a more complex example. Therefore, we should refer to the definition in a real-world scenario and solve it strictly mathematically. To express this problem with mathematical terms we use the ratio of f(n) to g(n) which is to be evaluated in the limit to +inf:

To simplify the calculation of the limit, divide each term in the numerator by n⁴:

As n approaches infinity (remember the example with the buckets), each term in the expression approaches 0 because the denominator grows faster than the numerator in each fraction:

Since the limit is 0, f(n) grows slower than g(n). To formally use this in the context of Big O notation:

• Choosing c: Any positive value of c would satisfy the condition f(n)≤c⋅g(n) for sufficiently large n because the growth rate of f(n) is so much slower.
• Finding n₀: The specific value of n₀​ would depend on the choice of c. However, the limit approach shows that such an n₀​ exists, which can be determined via a trial error or a visual approach as shown before.

Big Ω notation

Opposed to the Big O, the Big Omega (Ω) notation denotes the lower bound of an algorithm’s running time and space requirements. In the realm of computer science, we call it also the “best-case scenario”. Think of Big Omega as setting the floor for an algorithm’s performance. It’s like the guaranteed minimum performance you can expect. This is crucial because it helps us understand the least amount of resources an algorithm will require.

Why does this matter? It ensures that when planning or optimizing systems, we have a clear baseline of what to expect at the very least, avoiding underestimations that could lead to problems down the line. Essentially, Big Omega keeps our expectations realistic, providing a critical check on over-optimistic planning.

Mathematical definition

An algorithm is said to have a running time of Ω(f(n)) if there exists a positive constant c and a value n₀ such that for all input sizes n ≥ n₀, the running time of the algorithm is at least c * f(n).

f(n) is Ω(g(n)) if f(n) ≥ c * g(n), for every n > n₀

To bring the mathematical expression to life, we will set f(n) = 4n²+ 16n + 2 and g(n) = n². If f(n) is Ω(n²), means there are constants c and n₀​ such that for all n ≥ n₀, the running time of the algorithm is at least c * n². This establishes a best-case lower bound on the algorithm’s performance, indicating that no matter how optimized the algorithm becomes, its running time cannot drop below this quadratic growth rate for sufficiently large input sizes.

As a first step, we will illustrate these functions with an emphasis on behavior in the region of their intersection and beyond.

Our colonization provides an indication that after the intersection point is marked in red, f(n) grows faster than g(n). Also, The intersection of the two comes before the beginning of the axes, hence, we can choose n₀ ≥ 0 and c = 1.

Before proceeding to the mathematical approach, we can verify the plot by experimenting with a few values:

As the plot depicts, the table shows that for all sample points f(n) is greater than or equal to g(n), indicating that f(n) does grow faster than g(n)=n² in this range.

Mathematical definition

Similarly with Big O notation, we need to calculate the limit of f(n)/g(n) as n approaches infinity. The first step is to write the equation:

Then we will divide split the fraction:

Evaluate the limit of each term. As n approaches infinity, 16/n and 2/n² approach 0 because the denominators grow to infinity.

The result shows that f(n) increases at the same rate as g(n) in the long run. Both functions grow quadratically, the growth of f(n) is always four times that of g(n) when n is large enough. This implies that it is Ω(g(n)) for constant variables for c = 1 and n₀ = 0.

Big Θ notation

Big Theta (Θ) combines the ideas of Big O and Big Omega (Ω) notations to provide a more precise characterization of an algorithm’s performance. It is used to denote that an algorithm’s running time or space requirement grows within a range, for sufficiently large input sizes. Generally, it provides an estimation of the “average-case” scenario.

This kind of information is invaluable because it helps developers and engineers set realistic expectations and plan systems efficiently, knowing exactly what to expect in terms of performance. It’s a crucial tool for ensuring that the resources an algorithm requires are predictable and in line with the demands it faces.

Mathematical definition

Formally, we say that f(n) is Θ(g(n)) if there exist positive constants c1​,c2​, and n0​ such that for all n≥n₀:

c1​* g(n) ≤ f(n) ≤ c2 ​* g(n)

This definition implies that for sufficiently large n, the function f(n) is bounded both above and below by g(n) (up to constant factors). In other words, f(n) and g(n) grow at the same rate as n becomes large.

Let’s reuse our f(n) = 4n²+ 16n + 2 and a g(n) = n² functions to compare the growth rate. As mentioned, Big Θ is nothing more than a combination of the other two notations. Therefore, our goal is to solve this agile by proving the Big O and Ω in isolation.

Proving Big O

The Big O notation O(n²) means that f(n) does not grow faster than n² times some factor c2 for sufficiently large n. To prove that we need to find a constant such that it will satisfy the following inequality:

As we search for value n > 0, we can divide by n²:

Simplifies to:

Let’s examine the behaviour of the left part of the inequality as we approach the +inf:

The calculation shows that as n becomes very large, the left-hand side of the original inequality approaches 4. This means that to hold the inequity 12=01for all sufficiently large n, c2 must be at least 4.

Proving Big Ω

The Big Omega notation Ω(n²) means that f(n) grows at least as fast as n² times some constant factor, for sufficiently large n. We have already proved in the Big Ω section that for c = 1 and n₀ = 0, the inequality holds.

Proving Big Θ

Since n² satisfies both O(n²) and Ω(n²) we can conclude that f(n) is also Θ(n²). Moreover, I would like to take the time to demonstrate why this is the case.

There are some key takeaways that we need to extract from the plot. The most profound one is that n² holds an obviously lower boundary of the f(n). Next, the area that is painted with the yellow stripes is the possible range of performance of the algorithm that the big theta represents. Lastly, both 4*g(n) and f(n) have a quadratic growth rate as indicated by the n² term. The reason that looks like they overlap is that lim gave us the threshold that the differences between the functions are seamless when n goes to inf.

Examples of Space and Time Complexity

Let’s put into practice what we learnt. How do the software engineers benchmark algorithms?

Example O(1): Accessing an element in an array

Picture a bookshelf/list of items like a list of your favorite books. If you want to get the third book from the bookshelf you can directly go and access the third book and pick it up. This operation takes the same amount of time regardless of the books or the size of the shelf.

def access_element(arr, index):
    # Accessing an element by index in an array is an O(1) operation.
    return arr[index]

# Example usage:
books = ["The Great Gatsby", "1984", "To Kill a Mockingbird", "Moby Dick"]
index = 3
print(access_element(books, index))  # Output: "Moby Dick"

# The total complexity of the access_element function is O(1), constant time,
# because accessing an element at a specific index in a list (array) is a direct operation.

Time complexity: O(1)

Why?: Accessing an element by its index is a direct operation that doesn't depend on the size of the list.

Space complexity: O(1)

Why?: You don’t need extra space for this operation; you’re just reading an existing element.

Example (O(log n)): Accessing an element in an array

Suppose you have a sorted list of numbers: [1, 3, 5, 7, 9, 11, 13]. If someone asks you to find a specific item in the list, you won’t check each item individually. Instead, leveraging the fact that the array is sorted, you would use a recursive approach. You’d start by examining the middle item of the current array segment and determine whether the item is in the left or right half of the array.

In practice, we are being tasked to find number 11.

1. [1, 3, 5, 7, 9, 11, 13]: The middle term is 7. As 11 > 7, we will look at the right-hand side of the array.
2. [ 9, 11, 13 ] The middle term is 11, eureka!

In logn algorithms, software engineers like to demonstrate the stack calls via trees:

binary_search_recursive(arr, 11, 0, 7)
       (mid = 3, arr[3] = 7)
             /          \
          No call     binary_search_recursive(arr, 11, 4, 7)
                          (mid = 5, arr[5] = 11)
                            /          \
                         No call      Target found

The tree has provided the same information as before but in a digestible representation!

def binary_search_recursive(arr, target, left, right):
    # Base case: when the left index exceeds the right, the target is not found.
    # This step is O(1) because it only involves a simple comparison.
    if left > right:
        return -1
    
    # Calculate the middle index. This operation is O(1) as it involves basic arithmetic.
    mid = left + (right - left) // 2
    
    # Check if the middle element is the target. This comparison is also O(1).
    if arr[mid] == target:
        return mid
    
    # Recursive case: Decide whether to search in the left half or the right half.
    # This decision-making and the recursive call itself constitute the main part of the binary search logic.
    elif arr[mid] < target:
        # Recursive call to search in the right half of the array, which is O(log n) in the worst case.
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        # Recursive call to search in the left half of the array, which is also O(log n) in the worst case.
        return binary_search_recursive(arr, target, left, mid - 1)

# Example usage:
numbers = [1, 3, 5, 7, 9, 11, 13]
target = 11
print(binary_search_recursive(numbers, target, 0, len(numbers) - 1))  # Output: 5 (index of 11)

# Total complexity of the binary_search_recursive function is O(log n) where n is the number of elements in the array.
# This logarithmic time complexity arises because each recursive call approximately halves the size of the search space.

Time complexity: O(logn)

Why?: In the very beginning we have a guard check `left > right` this check is only O(1) as not affected by the input. Similarly, we calculate the mid-term in O(1). Consequently, the heavy work is related to the decision of whether to search right or left.

1. Initial size: n
2. After 1st division: n/2
3. After 2nd division: n/4
4. After 3rd division: n/8
5. …
6. After x divisions: n/x

The process repeats until the size becomes 1 (the target is found or the search space can no longer be divided).

Therefore, as the logarithmic section teaches you, we need to pose the question: “To what power must 2 be raised, to produce n?”.

2ˣ = n <=> log₂​n = x. Voila! Our search needs to perform O(logn) operations to find the target.

Space complexity: O(logn)

Why?: When a function is called in a programming language, it gets added to the call stack. This stack keeps track of active function calls. Each time `binary_search_recursive` is called, a new frame (containing the function's parameters, local variables, and return address) is added to the call stack. Once a function call completes, its frame is removed from the stack. The recursive calls add to the call stack, with each call using a constant amount of space. The depth of the call stack is proportional to log n.

Example (O(n)): Appending Elements to a Dynamic Array

Think of a dynamic array like a collection of photos on your phone. Each time you take a new photo, it gets added to the collection. If the current album is full, your phone might need to create a larger album and copy all existing photos to the new album.

def linear_search(arr, target):
    # This loop iterates over each element in the array, making it O(n) where n is the number of elements in the array.
    for i in range(len(arr)):
        # Check if the current element matches the target. This comparison is O(1).
        if arr[i] == target:
            return i  # Returns the index of the target if found, which is an O(1) operation.
    return -1  # Returns -1 if the target is not found, also an O(1) operation.

# Example usage:
names = ["Alice", "Bob", "Charlie", "David"]
target = "Charlie"
print(linear_search(names, target))  # Output: 2 (index of "Charlie")

# The total complexity of the linear_search function is O(n), since it potentially examines every element in the array once.
# This makes it less efficient than binary search for large datasets but simple and effective for small or unsorted arrays.

Time Complexity: O(n)

Why?: The primary component of the `linear_search` function is a for loop that iterates over every element in the array. The loop starts at the first element (i=0) and progresses sequentially through the array until the last element (i=len(arr)-1). Therefore, the worst-case scenario will be if the requested item is at the end of the list. Because it will require searching all the items on the list, hence O(n).

Space Complexity: O(n)

Why?: The space required grows linearly with the number of elements.

Example (O(2^n)): Fibonacci Sequence (Recursive)

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. A naive recursive algorithm for computing the nth Fibonacci number calls itself twice for each number, leading to a lot of repeated calculations.

def fibonacci(n):
    # Base case: when n is 0 or 1, return n. This is a direct O(1) operation.
    if n <= 1:
        return n
    
    # Recursive call: calculates Fibonacci of (n-1) and (n-2).
    # Each function call branches into two more calls, leading to exponential growth in the number of calls.
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # This is a major source of inefficiency without memoization.

# Example usage:
n = 5
print(fibonacci(n))  # Output: 5

# The time complexity of this naive recursive Fibonacci function is O(2^n).
# This exponential time complexity arises because each call generates two further calls, except at the base case.
# This leads to a doubling of calls at each level of recursion, forming a complete binary tree of calls.

Time Complexity: O(2^n)

Why?: Each call spawns two more calls, leading to exponential growth in the number of calls.

The number of calls at each level of recursion forms a sequence of powers of 2: 1, 2, 4, 8, …

                     F(n)
                     /  \
                  F(n-1) F(n-2)
                  /   \    /   \
              F(n-2) F(n-3) F(n-3) F(n-4)
               / \        / \     / \     
            ...   ...    ...   ...   ...   

• Level 0 (the top): 1 node, F(n).
• Level 1: 2 nodes, F(n-1) F(n-2).
• Level 2: 4 nodes, F(n-2) F(n-3) F(n-3) F(n-4).
• Level 3: 8 nodes, each decreasing by one in their Fibonacci call.
• …
• Level k (where k approaches n): 2ᵏ nodes.

The treewidth doubles with each additional level, reflecting the exponential growth in the number of calls, which is why the time complexity is O(2ⁿ).

Space Complexity: O(n)

Why?: The depth of the recursive call stack grows linearly with the input size. If every call were to store its result in an external structure without reusing memory, the space complexity could become O(2^n).

Conclusion

By reaching this point, you should be able to classify the time and space complexity of an algorithm and compare it with others. In this article, you learned how to lay a solid foundation with basic concepts and notations, which are essential for anyone diving into this field. From there, we delved into the mathematical underpinnings that help us comprehend how different functions grow and behave as input sizes increase. We then focused on the practical application of these principles, analyzing the time and space complexity of various algorithms.