Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding constant time complexity O(1)

Which of the following operations typically runs in constant time, O(1)?

A Accessing an element by index in an array

B Searching for an element in an unsorted list

C Sorting a list of numbers

D Traversing all elements in a linked list

💡 Hint

Think about operations that take the same amount of time regardless of input size.

Accessing an element by index in an array takes the same time no matter how big the array is, so it is O(1). Searching or traversing depends on the number of elements, so they are not constant time.

📋 Factual

intermediate

Identifying linear time complexity O(n)

Which scenario best represents an algorithm with linear time complexity O(n)?

A Accessing the last element of a fixed-size array

B Checking if a number is even or odd

C Calculating the sum of the first 100 numbers

D Finding a specific value by scanning each element in a list

💡 Hint

Consider how the time grows as the input size increases.

Scanning each element to find a value means the time grows directly with the number of elements, which is linear O(n). Checking even/odd or accessing fixed positions are constant time.

🔍 Analysis

advanced

Comparing logarithmic time complexity O(log n)

Which of the following algorithms typically runs in logarithmic time O(log n)?

A Binary search on a sorted array

B Linear search on an unsorted array

C Calculating the factorial of a number

D Bubble sort on a list

💡 Hint

Think about algorithms that repeatedly divide the problem size in half.

Binary search divides the search space in half each step, so it runs in O(log n). Linear search and bubble sort take longer as input grows, factorial calculation is not logarithmic.

🚀 Application

advanced

Recognizing quadratic time complexity O(n²)

Which example best illustrates an algorithm with quadratic time complexity O(n²)?

A A single loop that runs n times

B A recursive function that halves the input each call

C Nested loops where each loop runs n times

D Accessing elements in a hash table

💡 Hint

Consider how many times the inner operations run as input size grows.

Nested loops each running n times result in n × n = n² operations, which is quadratic time. Single loops are linear, recursive halving is logarithmic, and hash table access is constant time.

❓ Reasoning

expert

Determining time complexity from code snippet

What is the time complexity of the following code snippet?

def example_function(arr):
    for i in range(len(arr)):
        j = len(arr)
        while j > 0:
            j //= 2
            print(arr[i])

A O(log n)

B O(n log n)

C O(n)

D O(n²)

💡 Hint

Analyze how many times the inner while loop runs for each iteration of the outer for loop.

The outer loop runs n times. The inner while loop divides j by 2 each time, running about log n times. Multiplying gives O(n log n).

Practice

1. Which complexity class describes an algorithm that takes the same amount of time regardless of input size?

easy

A. O(n)

B. O(n²)

C. O(log n)

D. O(1)

Solution

1. Step 1: Understand what O(1) means

   O(1) means constant time, so the algorithm's time does not change with input size.

2. Step 2: Compare with other options

   O(n), O(log n), and O(n²) all depend on input size and grow as input grows.

3. Final Answer:

   O(1) -> Option D

4. Quick Check:

   Constant time = O(1) [OK]

Hint: Constant time means no input size effect [OK]

Common Mistakes:

• Confusing O(1) with O(n)
• Thinking O(log n) is constant
• Mixing up growth rates

2. Which of the following is the correct way to describe an algorithm with time complexity that doubles the work when the input size doubles?

easy

A. O(log n)

B. O(n²)

C. O(n)

D. O(1)

Solution

1. Step 1: Understand linear growth

   Doubling work when the input size doubles means time grows directly with input size, which is linear.

2. Step 2: Match with complexity classes

   O(n) means time grows linearly with input size, so it fits the description.

3. Final Answer:

   O(n) -> Option C

4. Quick Check:

   Linear growth = O(n) [OK]

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

Common Mistakes:

• Choosing O(log n) for linear growth
• Confusing O(n²) with linear
• Thinking O(1) grows with input

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(n²)

C. O(log n)

D. O(1)

Solution

1. Step 1: Analyze the outer loop

   The outer loop runs n times, from 0 to n-1.

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 iterations

   Total iterations = n (outer) * n (inner) = n².

4. Final Answer:

   O(n²) -> Option B

5. Quick Check:

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

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

Common Mistakes:

• Counting only one loop
• Thinking nested loops are O(n)
• Confusing with O(log n)

4. A programmer wrote this code to search for an element in a sorted list:

def search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return True
    return False

What is the main issue with this code regarding time complexity?

medium

A. It uses O(n) but could be improved to O(log n)

B. It uses O(log n) but should be O(n)

C. It uses O(n²) unnecessarily

D. It uses O(1) which is too fast

Solution

1. Step 1: Identify current complexity

   The code uses a simple loop over the list, so it is O(n).

2. Step 2: Consider the list is sorted

   For sorted lists, binary search can be used to reduce time to O(log n).

3. Final Answer:

   It uses O(n) but could be improved to O(log n) -> Option A

4. Quick Check:

   Linear search on sorted list = O(n), binary search = O(log n) [OK]

Hint: Use binary search on sorted lists for O(log n) [OK]

Common Mistakes:

• Thinking linear search is O(log n)
• Confusing O(n²) with O(n)
• Believing O(1) is possible here

5. You have a sorted list of 1,000,000 numbers and want to find if a number exists. Which algorithm choice is best for fastest average search time?

hard

A. Binary search on sorted list with O(log n) complexity

B. Linear search with O(n) complexity

C. Nested loops search with O(n²) complexity

D. Constant time search with O(1) complexity without extra data structures

Solution

1. Step 1: Evaluate linear search

   Linear search checks each element, O(n) = 1,000,000 steps on average.

2. Step 2: Evaluate binary search

   Binary search halves the search space each step, O(log n) ≈ 20 steps for 1,000,000 elements.

3. Step 3: Evaluate nested loops and constant time

   Nested loops O(n²) is very slow; O(1) without extra structures is unrealistic here.

4. Final Answer:

   Binary search on sorted list with O(log n) complexity -> Option A

5. Quick Check:

   Binary search fastest for large sorted lists = O(log n) [OK]

Hint: Binary search is fastest for large sorted lists [OK]

Common Mistakes:

• Choosing linear search for large data
• Expecting O(1) without extra structures
• Ignoring sorting requirement