Big O Notation

Objective: Explain Big O

Big O Notation is a way of representing just how long an algorithm takes to execute. It can determine the efficiency of different approaches in solving a problem using sorting and search algorithms. Types of Big O Notation:

O(1): Constant Time Complexity (Best case scenario)

Always take the same amount of time to be executed

Image Source: happycoders

O(n): Linear Time Complexity (How long your list is)

The time to execute the algoritm is proportional to the input size of n. The time to run increases as input size of n increases.

Image Souce: simplesnippets

O(log n): Logarithmic Time Complexity (Binary Search)

Takes a divide and conquer aproach. Splits the set in half, identifies which size has n then takes that side and repeats. Can only be done with a sorted list.

Image Source: pinterest

O(n^²): Quadratic Time Complexity (Bubble Sort)

Bubble sort works by repeatedly traversing a list swapping list positioning where needed on each pass. This can be seen in the form of nesting or nested loops where multiple passes through the list will continue until the list has been sorted. As you can imagine this is not the best approach.

Image Source: github

O(n log n): Merge Sort

Merge sort works in a similar approach to binary with a divide and conquer dividing the array in a temporary arrays and reformating and rebuilding the arrays in order.

Image Source: wikipedia

If you want to go deeper into Big O, check out bigocheatsheet

--

--

--

Developer

Love podcasts or audiobooks? Learn on the go with our new app.

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
Simon Leen

Simon Leen

Developer

More from Medium

Building a Game Engine From Scratch

Digital Twin as Code (DTaC)

Coordinate Systems of 3D Applications Guide

How to setup Git for a Unity project