Space and Time Complexity of An Algorithm

The complexity of an algorithm shows how fast or slow that particular algorithm can solve the desired problem. We can also define it as, it is a measurement of the amount of time and/or space required by an algorithm for a given input of size (n) to solve a problem. It provides a theoretical estimate of how the algorithm’s performance scales as the input grows. Complexity is typically expressed as a numerical function, T(n), which represents the time (or number of fundamental operations) required as a function of the input size n.

It’s important to note that the actual runtime of an algorithm can vary based on external factors like processor speed, disk I/O, compiler optimizations, and system architecture. Complexity analysis abstracts away these variables to give us a consistent, machine-independent way to compare algorithms.

Analyzing Complexity: Three Key Scenarios

1. Worst-Case Complexity

This represents the maximum amount of time or space an algorithm could require for any input of size n. We analyze the worst-case scenario to understand the upper bound on an algorithm’s resource usage, guaranteeing that performance will never be worse than this. It is determined by identifying the input that causes the algorithm to perform the maximum number of its primary operations.

2. Best-Case Complexity

This represents the minimum amount of time or space an algorithm requires for a specific, ideally favorable input of size n. For example, a sorting algorithm’s best case often occurs when the input is already sorted. While useful for understanding potential lower bounds, best-case analysis is often less practical as it rarely reflects typical usage.

3. Average-Case Complexity

This represents the expected time or space an algorithm requires for a random or typical input of size n. It is often the most meaningful measure for real-world performance, as it averages the cost over all possible inputs. However, it can be more difficult to calculate because it requires knowing the probability distribution of inputs.

Types of Complexity

1. Time Complexity
2. Space Complexity

1. Time Complexity

Time complexity describes how the runtime of an algorithm increases as the size of the input (n) grows. We express it using asymptotic notations, most commonly Big O notation (O), which describes the upper bound of an algorithm’s growth rate. In simple word we can say it as the time complexity of an algorithm gives the total amount of time taken by the program to complete its execution.

To calculate it, we count the number of times the algorithm’s dominant operation (like comparisons or assignments) is executed. This allows us to compare the efficiency of different algorithms abstractly, without running them on specific hardware.

Understanding Time Complexity with an Example

For any problem, there may be N number of solutions are available, but our main aim is to choose only those solutions which are efficient for our problem. Our solution should give the result in less time.

Let’s See the below example to understand this concept. Below are the two different algorithms to find a square of a number:

Algorithm 1: Using a Loop (Inefficient)

// Pseudo-code to calculate n² by adding n, n times
for i = 1 to n
    n = n + n
return n

This algorithm uses a for loop that iterates n times. In each iteration, it performs an addition. Therefore, the number of basic operations is directly proportional to n. We say its time complexity is O(n), or linear time. As n increases, the runtime increases linearly.

Algorithm 2: Using Multiplication (Efficient)

// Pseudo-code to calculate n² directly
return n * n

This algorithm performs a single multiplication operation. Regardless of how large n is, the work done is constant. Therefore, its time complexity is O(1), or constant time.

Conclusion: Algorithm 2 is far more efficient than Algorithm 1. Since worst-case analysis provides a performance guarantee, we generally use worst-case time complexity (expressed in Big O) to evaluate and compare algorithms.

2. Space Complexity

Space complexity analysis for an algorithm is an analysis to calculate the total amount of memory taken by an algorithm to complete execution and give the desired result for an input n. In space complexity analysis input value to the algorithm is also considered.

This includes memory for:

• The input values themselves.
• Variables, constants, and data structures used by the algorithm.
• The call stack used during execution (especially for recursive functions).

In simpler terms, it quantifies how much additional working memory an algorithm requires on top of the space needed to store the input.

Memory is consumed in several forms:

1. Variables & Constants: Storage for inputs, outputs, counters, and temporary results.
2. Program Instructions: The memory used to store the executable code itself.
3. Execution Stack: Memory used to manage function calls, return addresses, and local variables (crucial for recursion).

Space Complexity Example 1: Iterative Fibonacci

int fibonacci_iterative(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

• Constant Variables: The function uses a fixed number of variables (a, b, c, and i).
• No Recursion or Dynamic Allocation: There are no recursive calls or dynamic memory allocations.
• Space Complexity: The space required does not depend on the input n. It remains constant, leading to a space complexity of O(1), which is considered highly efficient in terms of space usage.

Space Complexity Example 2: Recursive Fibonacci

int fibonacci_recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

• Call Stack Growth: Each recursive call adds a frame to the call stack. Since the function calls itself twice for each non-base case, the number of calls grows exponentially with n. However, the maximum depth of the call stack at any given time is n.
• No Additional Memory Usage: Aside from the call stack, the function does not use additional memory (like arrays or dynamically allocated structures).
• Space Complexity: The space complexity is O(n) due to the call stack. For large n, this can lead to substantial memory usage, making it less space-efficient than the iterative approach.

Auxiliary Space vs. Total Space Complexity

Auxiliary Space refers specifically to the extra or temporary space an algorithm uses excluding the space taken by the input. It's the additional working memory needed for variables, temporary data structures, and the execution stack.

Total Space Complexity includes both the Auxiliary Space and the space required to store the input itself.

When we say "space complexity," we often refer to Auxiliary Space to focus on the algorithm's own memory overhead.

Memory Spaces Used by a Program

1. Instruction Space: It is used by the program to save compiled instruction in the memory. These are the actual machine-level or intermediate instructions that the CPU executes.
2. Environmental Stack:  This space is used to store return addresses, function call details, and control information when one module calls another (like in recursion or nested function calls).
   It maintains the execution context during function calls.
3. Data space: This is used to store variables, constants, and dynamically updated data used by the program during its execution.
   The data space grows or changes as the program progresses, depending on how the algorithm modifies or uses the data.