Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Time & Space Complexity

Time Complexity: Common complexity classes (O(1), O(n), O(log n), O(n²))

O(1), O(n), O(log n), O(n²)

Understanding Time Complexity

Time complexity helps us understand how the time to run a task changes as the input grows.

We want to know how fast or slow common patterns like constant, linear, logarithmic, and quadratic growth are.

Scenario Under Consideration

Look at these simple code examples showing different time complexities.

// O(1) - constant time
function getFirstItem(array) {
  return array[0];
}

// O(n) - linear time
function printAllItems(array) {
  for (let item of array) {
    console.log(item);
  }
}

// O(log n) - logarithmic time
function binarySearch(array, target) {
  let left = 0, right = array.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (array[mid] === target) return mid;
    else if (array[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// O(n²) - quadratic time
function printPairs(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      console.log(array[i], array[j]);
    }
  }
}
    

Each function shows a different way the number of steps grows with input size.

Identify Repeating Operations

Look at what repeats in each example:

• O(1): Just one step, no loops.
• O(n): One loop over all items, runs n times.
• O(log n): Loop cuts the problem size roughly in half each time, runs about log n times.
• O(n²): Two nested loops, each runs n times, total about n x n = n² times.

How Execution Grows With Input

Here is how the number of steps changes as input size grows:

Input Size (n)	O(1)	O(n)	O(log n)	O(n²)
10	1	10	~4	100
100	1	100	~7	10,000
1000	1	1000	~10	1,000,000

Notice how constant stays the same, linear grows steadily, logarithmic grows slowly, and quadratic grows very fast.

Final Time Complexity

Time Complexity: O(1), O(n), O(log n), O(n²)

These describe how the steps needed grow as input size grows, from fastest (constant) to slowest (quadratic).

Common Mistake

[X] Wrong: "Logarithmic time means the code runs instantly no matter the input size."

[OK] Correct: Logarithmic time still grows as input grows, just much slower than linear. It's fast but not instant.

Interview Connect

Understanding these common time complexities helps you explain how efficient your code is and shows you can think about performance clearly.

Self-Check

"What if we replaced the inner loop in the quadratic example with a loop that runs only half as many times? How would the time complexity change?"

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