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!)