Time complexity (Big O notation) in Data Structures Theory - Time & Space Complexity

Time Complexity: Time complexity (Big O notation)

O(n)

Understanding Time Complexity

Time complexity helps us understand how the time to run a program grows as the input gets bigger.

We want to know how the work done changes when we add more data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function sumArray(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

This code adds up all the numbers in an array and returns the total.

Identify Repeating Operations

• Primary operation: The for-loop that visits each item in the array once.
• How many times: Exactly once for each element in the array.

How Execution Grows With Input

As the array gets bigger, the number of steps grows in a straight line with the number of items.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: Doubling the input doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the size of the input.

Common Mistake

[X] Wrong: "The loop runs faster because it just adds numbers, so time doesn't grow much."

[OK] Correct: Even simple steps add up when repeated many times, so time still grows with input size.

Interview Connect

Understanding how time grows with input size helps you explain your code's efficiency clearly and confidently.

Self-Check

"What if we added a nested loop inside the first loop? How would the time complexity change?"