Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does O(1) mean in complexity classes?

O(1) means constant time complexity. The time to complete the task does not change no matter how big the input is. For example, accessing a single item in a list by its index.

beginner

Explain O(n) complexity with a real-life example.

O(n) means linear time complexity. The time grows directly with the size of the input. For example, checking each item in a shopping list one by one.

intermediate

What does O(log n) complexity represent?

O(log n) means logarithmic time complexity. The time grows slowly as input size increases, often by cutting the problem in half each step. For example, finding a word in a dictionary by opening near the middle and narrowing down.

intermediate

Describe O(n²) complexity and when it might happen.

O(n²) means quadratic time complexity. The time grows with the square of the input size. For example, comparing every student with every other student in a class to find pairs.

beginner

Why is understanding complexity classes important?

Understanding complexity helps us predict how fast or slow an algorithm will run as data grows. It helps choose efficient solutions and avoid slow programs.

Which complexity class means the running time does not change with input size?

A O(1)

B O(n)

C O(log n)

D O(n²)

O(1) means constant time, so the running time stays the same regardless of input size.

If an algorithm checks every item in a list once, what is its complexity?

A O(n)

B O(1)

C O(log n)

D O(n²)

Checking each item once means the time grows linearly with input size, which is O(n).

Which complexity is typical for binary search?

A O(n²)

B O(n)

C O(log n)

D O(1)

Binary search cuts the search space in half each step, leading to O(log n) complexity.

What does O(n²) complexity imply about the number of operations?

A Operations grow linearly

B Operations grow logarithmically

C Operations stay constant

D Operations grow with the square of input size

O(n²) means the number of operations grows with the square of the input size.

Why should we avoid algorithms with high complexity for large data?

A They run faster

B They can become very slow and inefficient

C They use less memory

D They are easier to understand

High complexity algorithms can become very slow as data grows, making them inefficient.

Explain the differences between O(1), O(n), O(log n), and O(n²) complexity classes with simple examples.

Think about how the time changes as input size grows.

Why is it important to understand complexity classes when choosing algorithms?

Consider the impact on speed and resources.

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