Time complexity (Big O notation) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Big O notation?

Big O notation is a way to describe how the time or space needed by an algorithm grows as the input size grows. It helps us understand the efficiency of algorithms.

beginner

What does O(1) time complexity mean?

O(1) means the algorithm takes the same amount of time to run, no matter how big the input is. This is called constant time.

intermediate

Explain the difference between O(n) and O(n²) time complexity.

O(n) means the time grows linearly with input size. O(n²) means the time grows much faster, roughly the square of the input size, which is slower for large inputs.

intermediate

Why do we ignore constants and lower order terms in Big O notation?

Because Big O focuses on how the algorithm behaves as input grows very large, constants and smaller terms become less important and don't affect the overall growth rate.

beginner

Give a real-life example to understand O(log n) time complexity.

Searching for a word in a dictionary by opening it in the middle and deciding which half to look next is like O(log n). Each step cuts the search space in half, making it very efficient.

Which of the following represents the fastest growing time complexity?

A O(n²)

B O(log n)

C O(1)

D O(n)

O(n²) grows faster than O(n), O(log n), and O(1) as input size increases.

What does O(n) mean in terms of algorithm performance?

A Time grows exponentially

B Time stays constant regardless of input

C Time grows linearly with input size

D Time grows logarithmically

O(n) means the time increases directly in proportion to the input size.

Why do we use Big O notation?

A To measure exact running time in seconds

B To describe how an algorithm scales with input size

C To count the number of lines in code

D To find bugs in the program

Big O notation describes how the running time or space needs grow as input size increases.

Which time complexity is better for large inputs?

A O(n²)

B O(n log n)

C O(n)

D O(1)

O(1) is the best because it does not grow with input size.

If an algorithm takes 5n + 10 steps, what is its Big O notation?

A O(n)

B O(5n + 10)

C O(10)

D O(n²)

Constants and smaller terms are ignored, so it simplifies to O(n).

Explain in your own words what Big O notation tells us about an algorithm.

Think about how time changes when input gets bigger.

Describe a real-life example that helps you understand O(log n) time complexity.

Consider how you find a word in a phone book or dictionary.

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