Time complexity (Big O notation) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Big O for Nested Loops

Consider a function that has two nested loops, each running from 1 to n. What is the time complexity of this function in Big O notation?

Data Structures Theory

for i in range(n):
    for j in range(n):
        do_something()

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

💡 Hint

Think about how many times the inner loop runs in total compared to the outer loop.

Each of the n iterations of the outer loop runs the inner loop n times, so the total operations are n * n = n², which is O(n²).

📋 Factual

intermediate

Time Complexity of Binary Search

What is the time complexity of the binary search algorithm on a sorted list of size n?

Data Structures Theory

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

A O(n)

B O(log n)

C O(n log n)

D O(1)

💡 Hint

Each step halves the search space.

Binary search divides the search space in half each iteration, so it runs in logarithmic time, O(log n).

🔍 Analysis

advanced

Analyzing Time Complexity of a Recursive Function

Given the recursive function below, what is its time complexity in Big O notation?

Data Structures Theory

def recursive_function(n):
    if n <= 1:
        return 1
    return recursive_function(n-1) + recursive_function(n-1)

A O(n^2)

B O(n)

C O(2^n)

D O(log n)

💡 Hint

Consider how many calls are made at each level of recursion.

This function calls itself twice for each call, doubling the number of calls at each level, leading to exponential growth, O(2^n).

❓ Comparison

advanced

Comparing Time Complexities of Sorting Algorithms

Which of the following sorting algorithms has the best average-case time complexity?

A Bubble Sort - O(n^2)

B Selection Sort - O(n^2)

C Insertion Sort - O(n^2)

D Merge Sort - O(n log n)

💡 Hint

Consider which algorithm uses divide and conquer.

Merge Sort uses divide and conquer and runs in O(n log n) time on average, which is faster than the O(n^2) average time of the others.

❓ Reasoning

expert

Determining Time Complexity from Code Output

What is the time complexity of the following code snippet?

Data Structures Theory

def mystery_function(n):
    i = 1
    count = 0
    while i < n:
        j = 0
        while j < i:
            count += 1
            j += 1
        i *= 2
    return count

A O(n)

B O(n log n)

C O(log n)

D O(n^2)

💡 Hint

Analyze how many times the inner loop runs as i grows exponentially.

The outer loop runs about log n times (because i doubles each time). The inner loop runs i times, which sums to about n overall, so total time is O(n).

Practice

1. What does O(n) time complexity mean in simple terms?

easy

A. The running time stays constant regardless of input size

B. The running time grows linearly with input size

C. The running time grows exponentially with input size

D. The running time grows logarithmically with input size

Solution

1. Step 1: Understand the meaning of O(n)

   O(n) means the time grows in direct proportion to the input size n.

2. Step 2: Compare with other growth types

   Unlike constant time O(1) or logarithmic O(log n), O(n) means if input doubles, time roughly doubles.

3. Final Answer:

   The running time grows linearly with input size -> Option B

4. Quick Check:

   Linear growth = O(n) [OK]

Hint: Linear means time grows directly with input size [OK]

Common Mistakes:

• Confusing O(n) with constant time O(1)
• Thinking O(n) means exponential growth
• Mixing up logarithmic and linear growth

2. Which of the following is the correct way to express constant time complexity in Big O notation?

easy

A. O(1)

B. O(n^2)

C. O(n)

D. O(log n)

Solution

1. Step 1: Recall constant time definition

   Constant time means the operation takes the same time regardless of input size.

2. Step 2: Match with Big O notation

   O(1) represents constant time complexity.

3. Final Answer:

   O(1) -> Option A

4. Quick Check:

   Constant time = O(1) [OK]

Hint: Constant time is always O(1) regardless of input [OK]

Common Mistakes:

• Choosing O(n) for constant time
• Confusing logarithmic with constant time
• Writing O(0) which is invalid

3. Consider the following code snippet:

for i in range(n):
    for j in range(n):
        print(i, j)

What is the time complexity of this code?

medium

A. O(n)

B. O(1)

C. O(n log n)

D. O(n^2)

Solution

1. Step 1: Analyze the outer loop

   The outer loop runs n times.

2. Step 2: Analyze the inner loop

   For each iteration of the outer loop, the inner loop runs n times.

3. Step 3: Calculate total operations

   Total operations = n * n = n², so time complexity is O(n^2).

4. Final Answer:

   O(n^2) -> Option D

5. Quick Check:

   Nested loops each running n times = O(n²) [OK]

Hint: Nested loops multiplying iterations = O(n²) [OK]

Common Mistakes:

• Counting only one loop's iterations
• Confusing O(n log n) with O(n²)
• Assuming constant time for nested loops

4. Identify the error in the following time complexity analysis:

def example(n):
    for i in range(n):
        for j in range(10):
            print(i, j)

Claimed time complexity: O(n^2). What is the correct time complexity?

medium

A. O(n)

B. O(1)

C. O(10n)

D. O(n^2)

Solution

1. Step 1: Analyze the outer loop

   The outer loop runs n times.

2. Step 2: Analyze the inner loop

   The inner loop runs a fixed 10 times, which is constant.

3. Step 3: Calculate total operations

   Total operations = n * 10 = 10n, which simplifies to O(n).

4. Final Answer:

   O(n) -> Option A

5. Quick Check:

   Fixed inner loop means linear time = O(n) [OK]

Hint: Ignore constants in Big O, fixed loops mean linear [OK]

Common Mistakes:

• Treating fixed inner loop as variable
• Writing O(n^2) without checking inner loop range
• Confusing constant factors with growth rates

5. You have a function that processes a list of n items. It first sorts the list using an efficient algorithm, then scans it once to find duplicates.
What is the overall time complexity of this function?

hard

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

Solution

1. Step 1: Analyze sorting step

   Efficient sorting algorithms like mergesort or heapsort run in O(n log n) time.

2. Step 2: Analyze scanning step

   Scanning the sorted list once is O(n).

3. Step 3: Combine complexities

   Total time is dominated by the slower step, which is sorting at O(n log n).

4. Final Answer:

   O(n log n) -> Option C

5. Quick Check:

   Sorting dominates scanning, so O(n log n) [OK]

Hint: Big O is max step time; sorting dominates scanning [OK]

Common Mistakes:

• Adding complexities instead of taking max
• Assuming scanning adds to sorting complexity
• Confusing sorting time with linear time