Space complexity analysis in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding space complexity of recursive functions

Consider a recursive function that calculates the factorial of a number n. What is the space complexity of this function in terms of n?

Data Structures Theory

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

A O(n^2) because the function multiplies n by factorial(n-1)

B O(1) because the function uses only a fixed amount of space

C O(n) because each recursive call adds a new layer to the call stack

D O(log n) because the recursion divides the problem size by 2 each time

💡 Hint

Think about how many times the function calls itself before reaching the base case and what happens to memory during these calls.

The recursive factorial function calls itself n times before reaching the base case. Each call adds a new frame to the call stack, so the space used grows linearly with n, resulting in O(n) space complexity.

📋 Factual

intermediate

Space complexity of iterative vs recursive algorithms

Which statement correctly compares the space complexity of an iterative algorithm and its recursive counterpart that solve the same problem?

A Iterative algorithms always use more space because they store all intermediate results

B Recursive algorithms use less space because they reuse the same variables

C Both have the same space complexity because they perform the same operations

D Recursive algorithms always use more space due to call stack overhead

💡 Hint

Consider what happens in memory when a recursive function calls itself multiple times.

Recursive algorithms use additional space for each call on the call stack, which can lead to higher space usage compared to iterative algorithms that reuse the same variables and do not add call stack frames.

🔍 Analysis

advanced

Analyzing space complexity of nested loops with data structures

Given the following pseudocode, what is the space complexity in terms of n?

Data Structures Theory

result = []
for i in range(n):
    temp = []
    for j in range(n):
        temp.append(i * j)
    result.append(temp)

A O(n^2) because a list of size n is created inside another list of size n

B O(n) because only one list is stored at a time

C O(1) because the space used does not depend on n

D O(n log n) because of the nested loops

💡 Hint

Consider how many elements are stored in total in the 'result' list after the loops finish.

The outer loop runs n times, and each time it creates a list 'temp' of size n. These n lists are stored inside 'result', so total space is proportional to n * n = n².

❓ Comparison

advanced

Comparing space complexity of different data structures

Which data structure generally uses the least space to store n elements?

A Binary tree because it stores nodes with multiple pointers

B Array because it stores elements contiguously without extra pointers

C Hash table because it stores keys and values with extra space for hashing

D Linked list because it stores only data and pointers

💡 Hint

Think about the overhead each data structure has beyond just storing the elements.

Arrays store elements contiguously in memory without extra pointers, so they use the least space per element. Linked lists and trees require extra pointers, and hash tables need additional space for hashing and handling collisions.

❓ Reasoning

expert

Determining space complexity of a function with dynamic data allocation

Consider a function that takes an integer n and creates a list of all prime numbers less than n. What is the expected space complexity of this function?

Data Structures Theory

def primes_less_than(n):
    primes = []
    for num in range(2, n):
        is_prime = True
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

A O(n / log n) because the prime number theorem estimates primes count near n / log n

B O(n) because the number of primes less than n grows approximately linearly

C O(log n) because only prime numbers are stored

D O(1) because the function uses a fixed amount of space regardless of n

💡 Hint

Recall the prime number theorem which estimates the number of primes less than a number n.

The prime number theorem states that the number of primes less than n is approximately n / log n. Since the function stores all these primes in a list, the space complexity is O(n / log n).

Practice

1. What does space complexity measure in an algorithm?

easy

A. The number of steps the algorithm performs

B. The time it takes for the algorithm to run

C. The number of errors the algorithm produces

D. The amount of memory the algorithm uses as input size grows

Solution

1. Step 1: Understand the definition of space complexity

   Space complexity refers to how much memory or storage an algorithm needs while running, especially as the input size increases.

2. Step 2: Differentiate from time complexity

   Time complexity measures how long an algorithm takes, not memory usage. Hence, space complexity is about memory.

3. Final Answer:

   The amount of memory the algorithm uses as input size grows -> Option D

4. Quick Check:

   Space complexity = memory usage [OK]

Hint: Space complexity = memory needed as input grows [OK]

Common Mistakes:

• Confusing space complexity with time complexity
• Thinking it measures steps or errors
• Ignoring memory usage in the definition

2. Which of the following correctly represents constant space complexity in Big O notation?

easy

A. O(n)

B. O(1)

C. O(n^2)

D. O(log n)

Solution

1. Step 1: Recall Big O notation for constant space

   Constant space means the algorithm uses the same amount of memory regardless of input size.

2. Step 2: Identify the notation for constant space

   O(1) means constant space, O(n) means linear, O(n^2) quadratic, and O(log n) logarithmic space.

3. Final Answer:

   O(1) -> Option B

4. Quick Check:

   Constant space = O(1) [OK]

Hint: Constant space always uses O(1) [OK]

Common Mistakes:

• Choosing O(n) for constant space
• Confusing time and space complexity notations
• Misunderstanding logarithmic space

3. Consider the following pseudocode:
function example(arr):
  temp = []
  for i in arr:
    temp.append(i)
  return temp
What is the space complexity of this function?

medium

A. O(n^2)

B. O(1)

C. O(n)

D. O(log n)

Solution

1. Step 1: Analyze memory usage for the temporary list

   The function creates a new list 'temp' and appends each element from input 'arr', so 'temp' grows linearly with input size n.

2. Step 2: Determine space complexity based on 'temp'

   Since 'temp' stores all elements, space used is proportional to n, so space complexity is O(n).

3. Final Answer:

   O(n) -> Option C

4. Quick Check:

   New list size = input size n -> O(n) space [OK]

Hint: Extra list storing all input means O(n) space [OK]

Common Mistakes:

• Assuming constant space because no nested loops
• Confusing time complexity with space complexity
• Ignoring the temporary list's size

4. Identify the error in the following code regarding space complexity:
def process(n):
  result = 0
  for i in range(n):
    temp = [0] * n
    result += sum(temp)
  return result
What is the space complexity and what is the mistake?

medium

A. O(n), mistake: temp list is recreated inside loop causing high memory use

B. O(1), mistake: temp list should be outside loop to save memory

C. O(n^2), mistake: temp list size grows each iteration

D. O(n), mistake: result variable should be a list

Solution

1. Step 1: Analyze space used by 'temp' inside the loop

   Each iteration creates a list 'temp' of size n, but it is discarded after the iteration ends, so peak memory is O(n).

2. Step 2: Identify the mistake in memory usage

   Recreating 'temp' inside the loop wastes memory repeatedly; better to create once outside the loop.

3. Final Answer:

   O(n), mistake: temp list is recreated inside loop causing high memory use -> Option A

4. Quick Check:

   Repeated list creation inside loop = O(n) space [OK]

Hint: Creating large lists inside loops wastes memory [OK]

Common Mistakes:

• Thinking space is O(1) because temp is local
• Assuming temp grows each iteration (it doesn't)
• Confusing time complexity with space complexity

5. You have a nested list of size n, where each element is a list of size n (an n x n matrix). You want to create a new list that contains the sum of each inner list. What is the space complexity of storing the sums?

hard

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

Solution

1. Step 1: Understand the input structure

   The input is an n x n matrix (list of n lists, each of size n), so total elements are n^2.

2. Step 2: Analyze the output list size

   The output list stores one sum per inner list, so it has n elements, which means space complexity is O(n).

3. Final Answer:

   O(n) -> Option A

4. Quick Check:

   One sum per inner list -> O(n) space [OK]

Hint: One value per inner list means O(n) space [OK]

Common Mistakes:

• Assuming output space is O(n^2) like input
• Confusing input size with output size
• Ignoring that sums reduce data size