Big-O Notation: Examples

Give a common example for each Big-O time complexity.

Answer

  • \(\mathbf{O(1)}\): Accessing an element in an array by index.

  • \(\mathbf{O(\log n)}\): Binary search on a sorted array.

  • \(\mathbf{O(\sqrt{n})}\): Finding all factor pairs of a number \(n\); a number can have at most \(\sqrt{n}\) distinct factor pairs.

  • \(\mathbf{O(n)}\): Iterating through an array to find a maximum or minimum value.

  • \(\mathbf{O(n \log n)}\): Efficient sorting algorithms.

  • \(\mathbf{O(n^2)}\): A nested for-loop.

  • \(\mathbf{O(n^3)}\): Three nested for-loops.

  • \(\mathbf{O(2^n)}\): Generating all subsets of a set (the power set).

  • \(\mathbf{O(n!)}\): Generating all permutations of an array of \(n\) elements.

Back to collection