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).