Day 1: Introduction & Big O Notation

What You'll Learn Today

• Fundamental concepts of algorithms and data structures
• Why learning algorithms matters
• Big O notation for expressing computational complexity
• Key complexity classes

---

What Is an Algorithm?

An algorithm is a well-defined set of steps to solve a specific problem. Like a recipe, it takes an input, executes a series of operations, and produces the expected output.

// Simple algorithm: find the largest number in an array
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

console.log(findMax([3, 7, 2, 9, 1])); // 9

---

What Is a Data Structure?

A data structure is a way of organizing and storing data. Choosing the right data structure can dramatically improve the efficiency of your algorithms.

flowchart TB
    subgraph DS["Data Structure Categories"]
        direction TB
        Linear["Linear"]
        NonLinear["Non-Linear"]
    end
    subgraph L["Linear"]
        A["Arrays"]
        B["Linked Lists"]
        C["Stacks"]
        D["Queues"]
    end
    subgraph NL["Non-Linear"]
        E["Trees"]
        F["Graphs"]
        G["Hash Tables"]
    end
    Linear --> L
    NonLinear --> NL
    style DS fill:#3b82f6,color:#fff
    style L fill:#22c55e,color:#fff
    style NL fill:#8b5cf6,color:#fff

---

Why Learn Algorithms?

The choice of algorithm can make a dramatic difference in performance when solving the same problem.

Example: Searching for a Value in a List

Linear Search: Check elements one by one from the beginning.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Binary Search: Repeatedly halve a sorted list to narrow down the target.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

When searching through 1 million elements:

• Linear search: Up to 1,000,000 comparisons
• Binary search: Up to 20 comparisons

Big O notation is how we express this difference precisely.

---

Big O Notation

Big O notation describes how an algorithm's running time or space usage grows as the input size n increases.

Drop Constants and Lower-Order Terms

Big O keeps only the most dominant term.

Exact Count	Big O
3n + 5	O(n)
2n² + 3n + 1	O(n²)
5	O(1)
n + log n	O(n)

---

Key Complexity Classes

flowchart LR
    subgraph Fast["Fast"]
        O1["O(1)\nConstant"]
        Olog["O(log n)\nLogarithmic"]
    end
    subgraph Medium["Moderate"]
        On["O(n)\nLinear"]
        Onlog["O(n log n)\nLinearithmic"]
    end
    subgraph Slow["Slow"]
        On2["O(n²)\nQuadratic"]
        O2n["O(2ⁿ)\nExponential"]
    end
    O1 --> Olog --> On --> Onlog --> On2 --> O2n
    style Fast fill:#22c55e,color:#fff
    style Medium fill:#f59e0b,color:#fff
    style Slow fill:#ef4444,color:#fff

O(1) - Constant Time

The operation completes in the same amount of time regardless of input size.

// Array access by index: O(1)
function getFirst(arr) {
  return arr[0];
}

O(log n) - Logarithmic Time

Doubling the input only adds one more step.

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

O(n) - Linear Time

Processing time grows proportionally with input size.

// Sum all elements: O(n)
function sum(arr) {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}

O(n log n) - Linearithmic Time

The typical complexity of efficient sorting algorithms.

// Merge sort: O(n log n)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

O(n²) - Quadratic Time

Occurs when nested loops iterate over the entire input twice.

// Bubble sort: O(n²)
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

O(2ⁿ) - Exponential Time

Each additional input element doubles the processing time.

// Fibonacci (naive recursive): O(2ⁿ)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

---

Runtime Comparison

For n = 1,000:

Complexity	Operations	Example
O(1)	1	Array index access
O(log n)	~10	Binary search
O(n)	1,000	Linear search
O(n log n)	~10,000	Merge sort
O(n²)	1,000,000	Bubble sort
O(2ⁿ)	Astronomical	Naive recursion

---

Space Complexity

Memory usage matters just as much as speed.

// O(1) space: in-place modification
function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

// O(n) space: creates a new array
function reverseNew(arr) {
  return arr.slice().reverse();
}

---

Summary

Concept	Description
Algorithm	A well-defined procedure for solving a problem
Data Structure	A method of organizing and storing data
Big O Notation	Notation expressing the growth rate of complexity
Time Complexity	How processing time scales with input
Space Complexity	How memory usage scales with input

Key Takeaways

1. Algorithm choice profoundly impacts execution speed
2. Big O notation expresses the worst-case growth rate
3. Constants and lower-order terms are dropped
4. Always consider the time-space tradeoff

---

Practice Problems

Problem 1: Basic

What is the time complexity of the following code in Big O notation?

function mystery(n) {
  let count = 0;
  for (let i = 1; i < n; i *= 2) {
    count++;
  }
  return count;
}

Problem 2: Intermediate

Determine the time complexity of the following code.

function process(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

Challenge

Implement an O(n) algorithm that finds a pair of elements in a sorted array whose sum equals a specific target value.

---

References

• Big O Cheat Sheet
• MDN - Array
• Wikipedia - Time complexity

---

Next up: In Day 2, we'll explore "Arrays & Linked Lists" — two fundamental data structures and when to use each one.