Time complexity (Big O notation) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Time complexity (Big O notation)

Start: Input size n

↓

Count basic operations

↓

Express operations as function f(n)

↓

Simplify f(n) to dominant term

↓

Represent as Big O notation

↓

Use Big O to compare algorithms

This flow shows how we analyze an algorithm's steps based on input size, simplify to the main factor, and express it as Big O to compare efficiency.

Execution Sample

Data Structures Theory

for i in range(n):
    print(i)

# Count operations for input size n

This code prints numbers from 0 to n-1, showing how operations grow with input size n.

Analysis Table

Iteration	i value	Operation Count	Condition	Action
1	0	1	0 < n	Print 0
2	1	2	1 < n	Print 1
3	2	3	2 < n	Print 2
...	...	...	...	...
n	n-1	n	n-1 < n	Print n-1
Exit	n	n	n < n is False	Stop loop

💡 Loop stops when i reaches n because condition i < n becomes false

State Tracker

Variable	Start	After 1	After 2	After 3	...	After n	Final
i	undefined	0	1	2	...	n-1	n
Operation Count	0	1	2	3	...	n	n

Key Insights - 3 Insights

Why do we ignore constants like 2n or 3n in Big O?

Big O focuses on the fastest growing term as input size grows large, so constants become insignificant compared to n. See execution_table where each iteration adds 1 operation, total n operations.

Why do we drop lower order terms like n + n^2 becomes O(n^2)?

Because n^2 grows faster than n as input increases, the n term becomes negligible. The dominant term defines Big O. This is why we simplify to the highest order term.

What does it mean if an algorithm is O(1)?

O(1) means the operation count does not grow with input size; it stays constant. Unlike the loop example where operations grow with n, O(1) stays the same no matter how big n is.

Visual Quiz - 3 Questions

Look at the execution_table, what is the operation count at iteration 3?

A 3

B 2

C 1

D n

💡 Hint

Check the 'Operation Count' column at iteration 3 in the execution_table.

At which iteration does the loop condition become false?

A At iteration n-1

B At iteration n

C At iteration 1

D Never

💡 Hint

Look at the 'Condition' column in the exit row of execution_table.

If the loop ran twice as many times, how would the operation count change?

A It would halve

B It would stay the same

C It would double

D It would square

💡 Hint

Refer to variable_tracker showing operation count grows linearly with iterations.

Concept Snapshot

Time complexity measures how an algorithm's steps grow with input size n.
Count basic operations, express as function f(n).
Simplify to dominant term, ignore constants and lower terms.
Represent with Big O notation like O(1), O(n), O(n^2).
Use Big O to compare efficiency of algorithms.

Full Transcript

Time complexity, expressed as Big O notation, shows how the number of steps an algorithm takes grows as the input size increases. We start by counting the basic operations an algorithm performs for input size n. Then, we express this count as a function f(n). To simplify, we keep only the dominant term that grows fastest as n increases, ignoring constants and smaller terms. This simplified form is called Big O notation, such as O(1) for constant time, O(n) for linear time, or O(n^2) for quadratic time. Big O helps us compare how efficient different algorithms are as inputs get large. For example, a loop running n times performs n operations, so its time complexity is O(n).

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