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?"