Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to represent the time complexity of accessing an element in an array.

Data Structures Theory

time_complexity = "O([1])"

Drag options to blanks, or click blank then click option'

A1

Bn

Clog n

Dn²

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing O(n) because they think it depends on the size of the array.

Confusing O(1) with O(log n).

Accessing an element in an array takes constant time, which is O(1).

2fill in blank

medium

Complete the code to represent the time complexity of searching for an element in an unsorted list.

Data Structures Theory

time_complexity = "O([1])"

Drag options to blanks, or click blank then click option'

A1

Bn²

Clog n

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing O(1) because they think search is instant.

Choosing O(log n) which applies to sorted data with binary search.

Searching in an unsorted list requires checking each element, so it takes O(n) time.

3fill in blank

hard

Fix the error in the code to represent the time complexity of binary search on a sorted list.

Data Structures Theory

time_complexity = "O([1])"

Drag options to blanks, or click blank then click option'

Alog n

Bn

C1

Dn²

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing O(n) which is linear search complexity.

Choosing O(1) which is constant time.

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

4fill in blank

hard

Fill both blanks to represent the time complexity of a nested loop iterating over n elements twice.

Data Structures Theory

time_complexity = "O([1][2])"

Drag options to blanks, or click blank then click option'

An

B1

C²

Dlog n

Attempts:

3 left

💡 Hint

Common Mistakes

Using O(n) instead of O(n²).

Using O(log n) which is incorrect for nested loops.

A nested loop over n elements twice results in O(n²) time complexity.

5fill in blank

hard

Fill all three blanks to create a dictionary showing time complexities for access, search, and binary search.

Data Structures Theory

complexities = {"access": "O([1])", "search": "O([2])", "binary_search": "O([3])"}

Drag options to blanks, or click blank then click option'

A1

Bn

Clog n

Dn²

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up the complexities for search and binary search.

Using O(n²) which is too slow for these operations.

Access is O(1), search in unsorted list is O(n), and binary search is O(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