Space Complexity in Algorithms

In this article learn what space complexity is, why memory usage matters, types of space complexity (O(1), O(n), O(log n), O(n²)), auxiliary vs total space, examples, and how to optimize algorithms for efficient memory use.

Space Complexity in Algorithms

What is Space Complexity?

Space Complexity is a measure of how much total memory an algorithm requires as the size of the input (n) increases.

It includes two types of memory:

1. Input Space – Memory needed to store the input.
2. Auxiliary Space – Extra memory needed during execution.

Note:
Like Time Complexity, Space Complexity is not measured in exact MB/GB.
It shows how memory usage grows with input size.

Why is Space Complexity Necessary?

• To avoid algorithms that consume excessive memory
• To design efficient programs for large datasets
• To develop memory-efficient algorithms for mobile/embedded systems
• To reduce auxiliary space during execution

What Does Space Complexity Measure?

1. Variables – Integers, floats, simple variables
2. Arrays / Lists – Memory for input and temporary arrays
3. Objects / Structures – Memory for user-defined data types
4. Recursion Stack – Memory used by recursive calls
5. Temporary Space – Memory used during intermediate computations (e.g., swapping)

Types of Space Complexity

1. Auxiliary Space
   Additional memory used by the algorithm excluding the input.
   • Example: Merge Sort requires O(n) extra space.
2. Total Space

Total Space=Input Space+Auxiliary Space\text{Total Space} = \text{Input Space} + \text{Auxiliary Space}Total Space=Input Space+Auxiliary Space

1. • Example:
     • Input array = n
     • Temporary array (Merge Sort) = n
     • Total = O(n + n) = O(2n) ≈ O(n)

Common Types of Space Complexity

1. O(1) – Constant Space (Best)
   Space does not depend on input size.
   • Examples:
     • Swapping two variables
     • Linear Search
     • Iterative algorithms
2. O(n) – Linear Space
   Space increases linearly with input size.
   • Examples:
     • Creating a new array
     • Merge Sort (Auxiliary Space)
     • BFS (Queue uses O(n) space)
3. O(log n) – Logarithmic Space
   Occurs in recursive algorithms with logarithmic stack depth.
   • Example:
     • Binary Search (recursive) → Stack depth = log n
4. O(n²) – Quadratic Space
   Used when storing a 2D matrix.
   • Examples:
     • n × n matrix
     • Graph adjacency matrix

Space Complexity Examples

Example 1: Constant Space

a = 10

b = 20

sum = a + b

→ Only 3 variables → O(1)

Example 2: Linear Space

int arr[n];

→ Stores n elements → O(n)

Example 3: Quadratic Space

int matrix[n][n];

→ n × n = n² elements → O(n²)

Example 4: Recursive Function

fact(n):

    if n == 1:

        return 1

    else:

        return n * fact(n-1)

Stack depth = n → O(n)

Example 5: Merge Sort

• Temporary array: O(n)
• Total space: O(n)

Space Complexity vs Time Complexity

Space–Time Trade-off

Sometimes:

• More space → less time
• Less space → more time

Example:

• Hash Table
  • Uses more memory
  • Lookup time becomes O(1) (very fast)

Conclusion

Space Complexity is an important part of algorithm analysis. It helps determine:

• How much memory a program requires
• Whether an algorithm will run on large datasets
• How suitable it is for low-memory systems (mobile, embedded)

Efficient algorithms are those that use less time and less space.

POP- Introduction to Programming Using ‘C’

DS – Data structure Using C

OOP – Object Oriented Programming 

Java Programming

DBMS – Database Management System

RDBMS – Relational Database Management System

https://defineinfoloop.blogspot.com/?m=1