Big O Notation: Practical Java Examples of the Big O Notation

Big O Notation

1. Overview

In this tutorial, we’ll talk about what Big O Notation means. We’ll go through a few examples to investigate its effect on the running time of your code.

2. The Intuition of Big O Notation

We often hear the performance of an algorithm described using Big O Notation.

3. Constant Time Algorithms — O(1)

How does this input size of an algorithm affect its running time? Key to understanding Big O is understanding the rates at which things can grow. The rate in question here is time taken per input size.

4. Logarithmic Time Algorithms — O(log n)

Constant time algorithms are (asymptotically) the quickest. Logarithmic time is the next quickest. Unfortunately, they’re a bit trickier to imagine.

5. Linear Time Algorithms — O(n)

After logarithmic time algorithms, we get the next fastest class: linear time algorithms.

Big O Notation Graphical Representation

6. N Log N Time Algorithms — O(n log n)

n log n is the next class of algorithms. The running time grows in proportion to n log n of the input:

7. Polynomial Time Algorithms — O(np)

Next up we’ve got polynomial time algorithms. These algorithms are even slower than n log n algorithms.

8. Exponential Time Algorithms — O(kn)

Now we are getting into dangerous territory; these algorithms grow in proportion to some factor exponentiated by the input size.

9. Factorial Time Algorithms — O(n!)

In most cases, this is pretty much as bad as it’ll get. This class of algorithms has a run time proportional to the factorial of the input size.

10. Asymptotic Functions

Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit — i.e. — when lots of input is thrown at it.

  • Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it’s a lower bound)
  • Finally, Big Θ describes the set of all algorithms that run at a certain speed (it’s like equality)

11. Conclusion

In this article, we discussed Big O notation, and how understanding the complexity of an algorithm can affect the running time of your code

Big O Notation

Software Developer