What is Time Complexity?

Big-O Time Complexities (Fastest to Slowest)

  • Constant Time

    • O(1)

    • Constant Running Time

    • Example Algorithms

      • Finding the median value in a sorted array of numbers

  • Logarithmic Time

    • O(log n)

    • Operations grow proportionally to the logarithm of the input size

      • 10 elements take x time

      • 100 elements take 2x time

      • 1000 elements take 4x time

      • 10000 elements take 16x time

    • Example Algorithms

      • Binary Search Time

  • Linear Time

    • O(n)

    • Run time grows linearly to the number

    • Example Algorithms

      • Finding the smallest or largest item in an unsorted array

      • Kadane’s algorithm

      • Linear Search

  • Linearithmic Time

    • O(n log n)

    • “The worst of the best time complexities”

    • Combination of linear time and logarithmic time

    • Floats around linear time until input reaches an advanced size

    • Example Algorithms

      • The best comparison sort algorithm

  • Quadratic Time

    • O(n^2)

  • Exponential Time

    • O(2^n)

  • Factorial Time

    • O(n!)