Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Common complexity classes (O(1), O(n), O(log n), O(n²))

Start: Input size n

↓

Choose algorithm

↓

Measure steps as function of n

↓

Classify complexity

↓

O(1): Constant steps

↓

O(log n): Steps grow slowly

↓

O(n): Steps grow linearly

↓

O(n²): Steps grow quadratically

↓

Predict performance for large n

↓

End

This flow shows how we start with input size, pick an algorithm, count steps, classify complexity, and predict performance.

Execution Sample

Data Structures Theory

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

This code prints pairs (i, j) for all i and j from 0 to n-1, showing O(n²) complexity.

Analysis Table

Step	i	j	Condition i<n	Condition j<n	Action	Output
1	0	0	0<3 True	0<3 True	Print (0,0)	(0,0)
2	0	1	0<3 True	1<3 True	Print (0,1)	(0,1)
3	0	2	0<3 True	2<3 True	Print (0,2)	(0,2)
4	0	3	0<3 True	3<3 False	Inner loop ends
5	1	0	1<3 True	0<3 True	Print (1,0)	(1,0)
6	1	1	1<3 True	1<3 True	Print (1,1)	(1,1)
7	1	2	1<3 True	2<3 True	Print (1,2)	(1,2)
8	1	3	1<3 True	3<3 False	Inner loop ends
9	2	0	2<3 True	0<3 True	Print (2,0)	(2,0)
10	2	1	2<3 True	1<3 True	Print (2,1)	(2,1)
11	2	2	2<3 True	2<3 True	Print (2,2)	(2,2)
12	2	3	2<3 True	3<3 False	Inner loop ends
13	3	-	3<3 False	-	Outer loop ends

💡 Outer loop i=3 fails condition i<n (3<3 is False), so loops end.

State Tracker

Variable	Start	After Step 1	After Step 4	After Step 8	After Step 12	Final
i	-	0	0	1	2	3
j	-	0	3	3	3	-

Key Insights - 3 Insights

Why does the inner loop reset j to 0 after it reaches n?

Because after j reaches n and the inner loop ends (see Step 4, 8, 12), the outer loop increments i and the inner loop starts again with j=0 (Step 5, 9). This is why j resets each time.

Why is this algorithm O(n²) and not O(n)?

Because for each of the n iterations of i, the inner loop runs n times, making total steps about n * n = n² (see execution_table rows 1-12).

What would happen if we removed the inner loop?

Then the steps would be just n (one loop), making complexity O(n). The execution_table would have fewer rows and j would not change.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7. What are the values of i and j?

A i=0, j=2

B i=1, j=2

C i=2, j=1

D i=1, j=1

💡 Hint

Check the 'i' and 'j' columns in execution_table row for Step 7.

At which step does the outer loop condition become false?

A Step 12

B Step 4

C Step 13

D Step 1

💡 Hint

Look at the 'Condition i

If n was increased to 4, how many total print actions would occur?

A 16

B 8

C 12

D 4

💡 Hint

Recall that total prints = n * n, see execution_table steps 1-12 for n=3.

Concept Snapshot

Common complexity classes:
O(1): Constant steps, no matter input size.
O(n): Steps grow linearly with input size.
O(log n): Steps grow slowly, halving input each time.
O(n²): Steps grow quadratically, nested loops.
Used to predict algorithm speed as input grows.

Full Transcript

This visual execution shows how algorithms behave with different input sizes n. We start with input size n, pick an algorithm, and count how many steps it takes. For example, nested loops cause steps to grow as n squared, shown by printing pairs (i, j) for i and j from 0 to n-1. The execution table traces each step, showing variable values and conditions. The variable tracker shows how i and j change over time. Key moments clarify why loops reset and why complexity is quadratic. The quiz tests understanding of variable values and loop endings. The snapshot summarizes common complexity classes and their meaning.

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