Performance Analysis in Algorithms — Understanding Space Complexity

-

When we study how good an algorithm is, we generally focus on performance analysis, which has two major components:

  1. Time Complexity – How long the algorithm takes to run.

  2. Space Complexity – How much extra memory the algorithm uses.

In this post, we will concentrate entirely on space complexity, because memory usage becomes a key factor when working with large data, recursion-heavy algorithms, or memory-constrained environments.

What Is Space Complexity?

Space complexity refers to the total memory an algorithm needs during execution, including input, variables, data structures, recursion stack, and auxiliary storage.

We calculate it using the formula:

Space = C + Sp

Where:

  • C (Fixed Part) – Memory required for constants, simple variables, fixed-size arrays, and program code. This does not change with input size.

  • Sp (Variable Part) – Memory that depends on the input size n, such as dynamic arrays, recursion stack frames, and temporary variables inside loops.

Understanding the Fixed Part (C)

The fixed part includes:

  • Basic variables like i, sum, temp

  • Constant-size arrays (e.g., int arr[10])

  • Instructions and compiled code

  • Memory required by the environment

This portion is independent of input size. Even if the input grows, C remains constant.

Example:
An algorithm that uses 3 integer variables will always take the same amount of memory, regardless of whether the input has 10 numbers or 10,000 numbers.

So C contributes O(1) to space complexity.

Understanding the Variable Part (Sp)

The variable part depends completely on the input. This includes:

  • Arrays whose size depends on n

  • Dynamic lists

  • Data structures built during execution

  • Memory used by recursive function calls

This is where actual space complexity grows from O(1) to O(n), O(log n), O(n²), etc.

Examples to Understand Space Complexity

Let’s explore examples starting from very basic to more advanced, covering both non-recursive and recursive algorithms.

1. Non-Recursive Example

Sum of first n numbers

Algorithm uses:

  • Three variables: i, n, sum

  • No extra storage based on input size

Space usage:
C = (memory for i, n, sum)
Sp = 0 (no variable-sized structure)

So Space = C + 0 = O(1)

This is constant space complexity.

2. Non-Recursive Example

Reading an array of size n

Algorithm uses:

  • Variables: i, n

  • Array of size n → depends on input

Space usage:
C = memory for fixed variables
Sp = memory for array of size n

Space = C + Sp = O(1) + O(n) = O(n)

This is linear space complexity.



3. Recursive Example

Factorial using recursion

Each recursive call requires:

  • Parameter n

  • Local variables inside the function

  • Return address

For n calls, recursion depth = n.

So space = C + Sp
C = constant variables
Sp = memory for n recursive stack frames = O(n)

So total = O(n) space.



4. Recursive Example

Merge Sort

Merge sort splits data into halves, recursively.

Space usage:

  • Temporary arrays used during merging ⇒ O(n)

  • Recursion depth = log n

  • Stack memory = O(log n)

Total space = O(n + log n) = O(n)
(We drop the smaller term.)

5. Recursive Example

Exponential recursion

Naive Fibonacci makes:

  • Two recursive calls per step

  • Recursion tree height = n

  • Stack grows to depth n

Space = O(n)
Time becomes exponential but space is still linear because stack depth grows linearly.

Why Space Complexity Matters

  • Recursion-heavy algorithms might run out of stack memory.

  • Large input sizes can crash programs if auxiliary arrays are too big.

  • Real-world constraints (mobile devices, embedded systems) require memory-efficient design.

  • Space vs Time tradeoffs appear frequently (like in dynamic programming).

Comments

Post a Comment

Popular posts from this blog

INTRODUCTION

-
Image
    What is an Algorithm? An algorithm is a clear and precise sequence of steps designed to solve a specific problem. It acts like a blueprint that tells the computer exactly what to do and in what order. Before writing any program in C, Python, or any language, you must first understand the algorithm you want to implement. Think of an algorithm as the “logic” behind a solution. The program is just the implementation of that logic. Understanding Algorithms Through Real Life Algorithms are not limited to computers.      We unknowingly use them in daily life. For example, consider the process of making tea : Boil water Add tea powder Add milk Add sugar Serve This is a perfect real-life algorithm — a sequence of steps that leads to a final outcome. Every step is clear, ordered, and must be followed correctly to get the desired result. A Simple Computer Example Imagine you are asked to find the largest number in a list of values. ...
Read more

Why Algorithms Matter: Understanding GCD Through Three Different Approaches

-
Image
 When we solve a problem in programming, there are always many ways to reach the same answer. But not all solutions are equal — some are slow, some are fast, and some are extremely efficient. This difference in how we solve a problem is exactly why algorithms matter. To understand this better, let’s look at a classic problem: 🧩 Problem: Find the GCD (Greatest Common Divisor) of two numbers We’ll solve it using three different techniques: Consecutive Integer Checking Algorithm Middle School Procedure (Prime Factorization) Euclid’s Algorithm By comparing them, you’ll clearly see why choosing the right algorithm matters .  Consecutive Integer Checking Algorithm (CICA) Idea: Start from the smallest of the two numbers and check downwards until you find a number that divides both. Example: Find GCD(56, 98) We start checking: 56? no 55? no 54? no ... 28? yes → it divides both. Final answer: 28 Algorithm: Let a and b be the two positive integers. ...
Read more