Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Mini Project: Build & Apply

Understanding Common Complexity Classes (O(1), O(n), O(log n), O(n²))

📖 Scenario: You are learning how different algorithms perform when the size of the input changes. This helps you understand how fast or slow a program might run in real life.

🎯 Goal: Build a simple guide that shows examples of four common complexity classes: O(1), O(n), O(log n), and O(n²). You will create data and explanations for each class step-by-step.

📋 What You'll Learn

Create a dictionary called complexity_examples with example descriptions for each complexity class.

Add a variable called input_size set to 1000 to represent the size of input.

Write a loop that goes through each complexity class in complexity_examples and creates a simple explanation string using input_size.

Add a final summary string called summary that explains why understanding these classes is useful.

💡 Why This Matters

🌍 Real World

Understanding complexity classes helps developers choose efficient algorithms for tasks like searching, sorting, and data processing.

💼 Career

Software engineers and data scientists use complexity analysis to write faster and more scalable code.

1

Create the complexity examples dictionary

Create a dictionary called complexity_examples with these exact entries: 'O(1)': 'Accessing an element in an array by index', 'O(n)': 'Finding an item in an unsorted list', 'O(log n)': 'Binary search in a sorted list', and 'O(n²)': 'Checking all pairs in a list'.

Data Structures Theory

# Create the dictionary complexity_examples with the given entries
# Your code here

Hint

Use curly braces {} to create a dictionary with keys as complexity classes and values as example descriptions.

2

Set the input size variable

Create a variable called input_size and set it to 1000 to represent the size of the input data.

Data Structures Theory

complexity_examples = {
    'O(1)': 'Accessing an element in an array by index',
    'O(n)': 'Finding an item in an unsorted list',
    'O(log n)': 'Binary search in a sorted list',
    'O(n²)': 'Checking all pairs in a list'
}
# Create the variable input_size and set it to 1000
# Your code here

Hint

Just assign the number 1000 to the variable input_size.

3

Create explanations using a loop

Write a for loop using variables complexity and example to iterate over complexity_examples.items(). Inside the loop, create a new dictionary called explanations where each key is complexity and the value is a string combining the example and the input size like this: f"{example} for input size {input_size}".

Data Structures Theory

complexity_examples = {
    'O(1)': 'Accessing an element in an array by index',
    'O(n)': 'Finding an item in an unsorted list',
    'O(log n)': 'Binary search in a sorted list',
    'O(n²)': 'Checking all pairs in a list'
}

input_size = 1000

explanations = {}
# Use a for loop with complexity and example to fill explanations
# Your code here

Hint

Use a for loop to go through each item in the dictionary and build a new dictionary with formatted strings.

4

Add a summary explanation

Create a string variable called summary with this exact text: 'Understanding these complexity classes helps predict how algorithms perform as data grows.'

Data Structures Theory

complexity_examples = {
    'O(1)': 'Accessing an element in an array by index',
    'O(n)': 'Finding an item in an unsorted list',
    'O(log n)': 'Binary search in a sorted list',
    'O(n²)': 'Checking all pairs in a list'
}

input_size = 1000

explanations = {}
for complexity, example in complexity_examples.items():
    explanations[complexity] = f"{example} for input size {input_size}"

# Create the summary string with the exact text
# Your code here

Hint

Assign the exact sentence to the variable summary.

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