A Quick Overview of Big O Notation

Braxton Massengale
Feb 14 · 4 min read

Introduction

If you’re studying computer science or software engineering then no doubt when discussing algorithms you’re very likely to hear about Big O notation. But what is it and why do you need to know it? Let’s discuss.

Big O notation is simply a measure of the time complexity of an algorithm. In other words, if we increase the data that we input into an algorithm how does it affect the speed of computation? For example if we have an algorithm that processes x amount of data in y amount of time, we want to know what at what rate more or less y would increase by if we introduced 2x, 3x, x2 , etc. amount of data. This is the purpose that Big O notation serves, to estimate how the speed of an algorithm’s computation is affected relative to the input value. It’s important to note that big O is not used to calculate how long a computation will take in absolute terms. It is only concerned with the relative speed of the computation. This post is meant to serve as an overview for the four most often discussed time complexities.

O(1) — Constant

A Big O notation of O(1) means that the time complexity of the algorithm is constant. In other words, the size of the input data does not have an affect on the speed of the algorithm. An example of O(1) or constant time complexity would be accessing an element of an array. The time it takes to execute does not depend on the size of the input data.

Java code showing an array
Java code showing an array

O(n) — Linear

A Big O notation of O(n) means that the time complexity of the algorithm is linear. This means that the time it takes for this algorithm to execute is proportional to the the input data. As a rough example, if the value of n is 3 and it takes 3 milliseconds to execute then with an input value of 5 for n, we could expect that the computation would take about 5 milliseconds. An example of O(n) or linear time complexity would be a simple for loop.

Java code showing a for loop
Java code showing a for loop

O(log (n)) — Logarithmic

A Big O notation of O(log (n)) means that the time complexity of the algorithm is logarithmic, meaning that the time complexity is proportional to the logarithm of n. In case you need a refresher on what a logarithm is, here’s a link to a couple of Khan Academy videos discussing logarithms. An algorithm with logarithmic time complexity can be thought of as a divide and conquer approach such as the famous phone book example from Harvard’s CS50 course. An example of O(log (n)) or logarithmic time complexity would be binary search.

A graphic demonstrating binary search
A graphic demonstrating binary search

O(n^2) — Quadratic

A Big O notation of O(n^2) means that the time complexity of the algorithm is quadratic, meaning that the time complexity is proportional to the square of n. An example of a O(n^2) or quadratic time complexity would be a nested for loop. This can actually go deeper if there are even more nested loops n^3 and so on, depending on the number of nested loops.

Java code showing a nested for loop
Java code showing a nested for loop

To better understand these time complexities, it’s often helpful to see them on a graph. Here’s a graph that demonstrates how various time complexities perform based on the number of input elements. This graph has the four time complexities discussed in this post as well as a few others.

A graph which shows various time complexities
A graph which shows various time complexities

Recap

To quickly recap the four most common types of time complexity:

  • O(1) is a constant time complexity
  • O(n) is a linear time complexity
  • O(log (n)) is a logarithmic time complexity
  • O(n2) is a quadratic time complexity

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data…

Sign up for Analytics Vidhya News Bytes

By Analytics Vidhya

Latest news from Analytics Vidhya on our Hackathons and some of our best articles! Take a look.

Check your inbox
Medium sent you an email at to complete your subscription.

Braxton Massengale

Written by

Hey, I’m an American software developer living in Spain. I like to read and write about software development and technology!

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

Braxton Massengale

Written by

Hey, I’m an American software developer living in Spain. I like to read and write about software development and technology!

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store