Algorithm efficiency & Big O

Two different algorithms may both produce the correct result, but one might complete in milliseconds while the other takes hours.Algorithm efficiency measures the computational resources (execution time and memory space) consumed by an algorithm as input size $n$ grows.

We use Big O notation to categorize algorithms by their worst-case asymptotic growth rate:

• $O(1)$ : Constant time: Execution time does not depend on dataset size. Examples include reading an array index (arr[i]), pushing onto a stack, or simple arithmetic.
• $O(\log n)$ : Logarithmic time: The problem space is divided by two on each step. Highly efficient even for billions of records. Example: Binary Search.
• $O(n)$ : Linear time: Operations scale in direct proportion to input size. Example: Linear search iterating through an unsorted list.
• $O(n \log n)$ : Linearithmic time: The fastest possible comparison-based sorting algorithms (Merge Sort, Quick Sort).
• $O(n^2)$ : Quadratic time: Operations scale with the square of input size, typical of nested loops comparing every pair of elements. Examples: Bubble Sort, Selection Sort.
• $O(2^n)$ : Exponential time: Operations double with each added item. Quickly becomes intractable for large inputs.

Time complexity tracks how the number of instructions executed scales with $n$.Space complexity tracks the extra working RAM (excluding initial input storage) required during execution. For example, Bubble sort uses $O(1)$ auxiliary space because it swaps elements in place, whereas Merge sort requires $O(n)$ extra memory to hold temporary halves.