📅 Day 2: Big O Notation – O(1), O(n), O(n²)

🧠 Concept Deep Dive

Big O notation helps us understand how the performance of an algorithm scales with the input size n. It focuses on the worst-case scenario, describing how many operations the algorithm takes as the input grows.

Let's break down the common Big O complexities you’ll encounter:

Big O	Name	Explanation	Example
O(1)	Constant Time	The operation takes the same amount of time regardless of input size	Accessing an element by index
O(n)	Linear Time	Time grows linearly with input size — if input doubles, time doubles	Looping through an array
O(n²)	Quadratic Time	Time grows with the square of the input size — nested loops over input	Comparing all pairs in an array

Why Does This Matter?

Efficiency: When working with large datasets, algorithms with lower Big O will be much faster.
Predictability: Big O helps predict how your code will perform as data scales.
Optimization: Understanding complexity guides you to write better, scalable code.

👨‍💻 Code Examples

O(1) – Constant Time

Accessing an element by index in an array takes constant time because you jump directly to it, no matter how big the array is.

function getFirstElement(arr: number[]): number | undefined {
  return arr[0];  // Always takes the same time, O(1)
}

// Test
console.log(getFirstElement([10, 20, 30])); // Output: 10

O(n) – Linear Time

Looping through an array to calculate the sum of its elements takes time proportional to the number of elements.

function sumArray(arr: number[]): number {
  let sum = 0;                // O(1)
  for (let i = 0; i < arr.length; i++) {  // O(n)
    sum += arr[i];
  }
  return sum;
}

// Test
console.log(sumArray([1, 2, 3, 4])); // Output: 10

O(n²) – Quadratic Time

When you have nested loops over the same array, the time complexity multiplies.

function printAllPairs(arr: number[]): void {
  for (let i = 0; i < arr.length; i++) {       // O(n)
    for (let j = 0; j < arr.length; j++) {     // O(n)
      console.log(arr[i], arr[j]);              // O(1)
    }
  }
}

// Test
printAllPairs([1, 2, 3]);
// Output:
// 1 1
// 1 2
// 1 3
// 2 1
// 2 2
// 2 3
// 3 1
// 3 2
// 3 3

📊 ASCII Traces

O(1) – Constant Time

Input: [5, 10, 15]

Access arr[0] → 5

Time taken: Same no matter array size

O(n) – Linear Time

Input: [1, 2, 3]

Sum elements:

1 + 2 + 3 = 6

Time taken: Proportional to n (3 steps)

O(n²) – Quadratic Time

Input: [1, 2, 3]

Pairs generated (nested loops):

(1,1), (1,2), (1,3)
(2,1), (2,2), (2,3)
(3,1), (3,2), (3,3)

Time taken: Number of operations ≈ n * n = 9

🏁 Homework (LeetCode-style)

Problem: Count all unique pairs `(i, j)` in an array where `i != j`

Function Signature:

function countPairs(arr: number[]): number;

Constraints:

Array length can be from 1 to 10,000.
Elements are integers.
Count all ordered pairs (i, j), where i and j are indices, and i !== j.

Example 1:

Input: [1, 2, 3]
Output: 6
Explanation: Pairs are (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

Example 2:

Input: [4, 4]
Output: 2
Explanation: Pairs are (0,1), (1,0)

🧠 Bảng tóm tắt Big O

Operation	Time Complexity	Explanation
Access by Index	O(1)	Direct access to an element
Loop through array	O(n)	One pass through the data
Nested loops	O(n²)	Comparing each pair of elements

🧾 Summary

Big O helps predict how your algorithm performs as data size grows.
O(1) means constant time — super fast, no matter input size.
O(n) means linear time — time grows proportionally with input.
O(n²) means quadratic time — time grows fast due to nested loops.
Understanding Big O is essential for writing efficient algorithms!

🔜 Coming Up

📅 Day 3: Arrays – Indexing, Iteration, and Basic Operations

We'll learn how arrays work internally, how to iterate them efficiently, and basic operations every programmer should know.