Time complexity (Big O notation) in Data Structures Theory - Mini Project: Build & Apply

Understanding Time Complexity (Big O notation)

📖 Scenario: You are learning how to analyze the efficiency of simple algorithms by understanding their time complexity using Big O notation. This helps you know how the time to complete a task grows as the input size increases.

🎯 Goal: Build a simple example that shows how to count items in a list and understand the time complexity of this operation.

📋 What You'll Learn

Create a list of exactly 5 fruit names

Create a variable to count how many fruits start with the letter 'A'

Use a for loop to check each fruit and update the count

Add a final statement that represents the time complexity of this counting operation

💡 Why This Matters

🌍 Real World

Understanding time complexity helps you write efficient programs that run faster and handle large data well.

💼 Career

Many tech jobs require analyzing and improving algorithm efficiency to optimize software performance.

1

Create the list of fruits

Create a list called fruits with these exact entries: 'Apple', 'Banana', 'Avocado', 'Cherry', 'Apricot'.

Data Structures Theory

# Create the list called fruits with the given fruit names
# Your code here

Hint

Use square brackets [] to create a list and separate items with commas.

2

Create a counter variable

Create a variable called count_a and set it to 0. This will count fruits starting with the letter 'A'.

Data Structures Theory

fruits = ['Apple', 'Banana', 'Avocado', 'Cherry', 'Apricot']
# Create count_a variable and set it to 0
# Your code here

Hint

Use a simple assignment to create the counter variable.

3

Count fruits starting with 'A'

Use a for loop with variable fruit to go through fruits. Inside the loop, use an if statement to check if fruit starts with the letter 'A'. If yes, increase count_a by 1.

Data Structures Theory

fruits = ['Apple', 'Banana', 'Avocado', 'Cherry', 'Apricot']
count_a = 0
# Use a for loop to check each fruit and update count_a
# Your code here

Hint

Use the startswith() method to check the first letter of the fruit.

4

Add the time complexity comment

Add a comment line that states the time complexity of this counting operation as # Time complexity: O(n) where n is the number of fruits.

Data Structures Theory

fruits = ['Apple', 'Banana', 'Avocado', 'Cherry', 'Apricot']
count_a = 0
for fruit in fruits:
    if fruit.startswith('A'):
        count_a += 1
# Add the time complexity comment below
# Your code here

Hint

This means the time grows linearly with the number of items.

Practice

1. What does O(n) time complexity mean in simple terms?

easy

A. The running time stays constant regardless of input size

B. The running time grows linearly with input size

C. The running time grows exponentially with input size

D. The running time grows logarithmically with input size

Solution

1. Step 1: Understand the meaning of O(n)

   O(n) means the time grows in direct proportion to the input size n.

2. Step 2: Compare with other growth types

   Unlike constant time O(1) or logarithmic O(log n), O(n) means if input doubles, time roughly doubles.

3. Final Answer:

   The running time grows linearly with input size -> Option B

4. Quick Check:

   Linear growth = O(n) [OK]

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

Common Mistakes:

• Confusing O(n) with constant time O(1)
• Thinking O(n) means exponential growth
• Mixing up logarithmic and linear growth

2. Which of the following is the correct way to express constant time complexity in Big O notation?

easy

A. O(1)

B. O(n^2)

C. O(n)

D. O(log n)

Solution

1. Step 1: Recall constant time definition

   Constant time means the operation takes the same time regardless of input size.

2. Step 2: Match with Big O notation

   O(1) represents constant time complexity.

3. Final Answer:

   O(1) -> Option A

4. Quick Check:

   Constant time = O(1) [OK]

Hint: Constant time is always O(1) regardless of input [OK]

Common Mistakes:

• Choosing O(n) for constant time
• Confusing logarithmic with constant time
• Writing O(0) which is invalid

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(1)

C. O(n log n)

D. O(n^2)

Solution

1. Step 1: Analyze the outer loop

   The outer loop runs n times.

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 operations

   Total operations = n * n = n², so time complexity is O(n^2).

4. Final Answer:

   O(n^2) -> Option D

5. Quick Check:

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

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

Common Mistakes:

• Counting only one loop's iterations
• Confusing O(n log n) with O(n²)
• Assuming constant time for nested loops

4. Identify the error in the following time complexity analysis:

def example(n):
    for i in range(n):
        for j in range(10):
            print(i, j)

Claimed time complexity: O(n^2). What is the correct time complexity?

medium

A. O(n)

B. O(1)

C. O(10n)

D. O(n^2)

Solution

1. Step 1: Analyze the outer loop

   The outer loop runs n times.

2. Step 2: Analyze the inner loop

   The inner loop runs a fixed 10 times, which is constant.

3. Step 3: Calculate total operations

   Total operations = n * 10 = 10n, which simplifies to O(n).

4. Final Answer:

   O(n) -> Option A

5. Quick Check:

   Fixed inner loop means linear time = O(n) [OK]

Hint: Ignore constants in Big O, fixed loops mean linear [OK]

Common Mistakes:

• Treating fixed inner loop as variable
• Writing O(n^2) without checking inner loop range
• Confusing constant factors with growth rates

5. You have a function that processes a list of n items. It first sorts the list using an efficient algorithm, then scans it once to find duplicates.
What is the overall time complexity of this function?

hard

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

Solution

1. Step 1: Analyze sorting step

   Efficient sorting algorithms like mergesort or heapsort run in O(n log n) time.

2. Step 2: Analyze scanning step

   Scanning the sorted list once is O(n).

3. Step 3: Combine complexities

   Total time is dominated by the slower step, which is sorting at O(n log n).

4. Final Answer:

   O(n log n) -> Option C

5. Quick Check:

   Sorting dominates scanning, so O(n log n) [OK]

Hint: Big O is max step time; sorting dominates scanning [OK]

Common Mistakes:

• Adding complexities instead of taking max
• Assuming scanning adds to sorting complexity
• Confusing sorting time with linear time