• March 23, 2023
Big O Notation - How to Identify efficient algorithms

Big O Notation helps Software Engineers understand the impact of the algorithms they write.

This concept is vital to understanding how to label your algorithm’s efficiency using Big O Notation.

But how do we know the notation of each algorithm?

We use the Growth Hierarchy for Big O Notation

If you’re wondering what Big O Notation is, check out my previous article where the topic is covered in detail.

The growth hierarchy ranks the efficiency of a notation used to identify an algorithm.

Think of an electrical appliance efficiency rating. Rather than using an A-G rating, we use notations for algorithms:

In Software Engineering we want to write algorithms that are efficient in time and space complexity.

Efficient algorithms process input at a fast rate (time complexity) and with minimal memory (space complexity), so that when our application grows we spend less money on resources to run the code.

The three most efficient notations are:

  • Constant Notation
  • Logarithmic Notation
  • Linear Notation

How to identify a Constant, Logarithmic, and Linear Notation?

For each notation there are a set of rules we use to identify them:

Constant Notation

A constant notation means a value does not change despite the input increasing.

In software engineering constants are normally hard coded values, which do not change no matter the size of the input.

Think of a constant as ‘constantly the same’.

Real Life Scenario – Clothes Shop

Jen is looking to buy a jumper from her favourite clothes shop.

This clothes shop has the same size guides for all their clothing, meaning that all medium jumpers are the same regardless of style.

She knows she is a medium as she knows her measurements exactly.

It does not matter if the shop adds twenty more sizes as she knows that the medium fits her perfectly. Jen just needs to pick up a medium jumper and she can make her purchase, without acknowledging the other sizes.

This is a constant notation. Jen has her size noted down and she does not care about all the sizes. Think of the different sizes as the amount of input.

PHP Example

Comparing the clothing shop example to a code example. A constant guarantees the same execution time and memory regardless of the amount of input, as the code is the same every time.

With code, we can assume that hard-coded values are constant notations.

Here is an example of constant notation:

Big O Notation - Constant Function
Constant Notation

The code above is a simple function which accepts an integer as an input and prints out the text:

‘The number of customers in the shop is: ‘ – with the input attached at the end.

This is a constant, as no matter what the size of the input is, we can guarantee that one line of text will be output every time.

Logarithmic

A logarithmic algorithm is the second most efficient algorithm.

The amount of time and space required grows as the input grows, but this occurs slowly. And the size of the input should halve with every iteration of the algorithm.

This typically occurs with the following scenario:

  • The algorithm is searching for a specific item – a specific number among a list of numbers for example.
  • The list of items we are looking through are in ascending or descending order.

Logarithmic algorithms use divide and conquer to eliminate half of the unwanted input at every step, which is typically seen in a Binary Search algorithm.

So how do we apply a logarithmic algorithm in a real world context?

Real Life Scenario – Choosing the correct size of clothing

Jen is in a clothes store looking to buy a new jumper.

There are nine different sizes of the jumper she wants, and she has no idea what size she is. Rather than trying every size from smallest to largest, she uses divide and conquer.

So Jen grabs the medium size and puts the other sizes into two groups. The smaller group of jumpers (group 1 – smaller than a medium), and the larger group of jumpers (group 2 – larger than a medium).

Hopefully the medium fits just right, but if not she can look at one of the two groups.

If the medium is too big, Jen knows that a smaller size is needed and she will look in group 1, but if a larger size is needed, she will look at group 2, discarding the other group.

Big O Notation - Splitting jumper sizes into two groups
Splitting the jumper sizes into two groups.

Jen tries on the medium and realises that it is too small and will need to look at group 2.

Rather than starting with the L size, she look in the middle and rounds up (favouring the larger size if there is an even number) – going for the XXL and splitting the remainder sizes into two groups again:

As the XXL is too large, she now looks at group 1 as these items are smaller and she picks the larger item out of the two (rounding up if the numbers are even).

Jen realises that the XL is the perfect size and she stops here.

Big O Notation - Splitting jumper sizes into two groups
Binary Search – Finding the correct size of clothing

Now to find the perfect size Jen had to try on three items of clothing.

If she tried the clothes in order of sizing, starting with the smallest, it would have taken 7 attempts (assuming she stops at XL and does not try XXL or XXXL).

By using divide and conquer we can reduce unnecessary steps rather than going through every input.

PHP Example

The example of divide and conquer, is a common algorithm used in Software Engineering known as a Binary Search.

This relies on two factors:

  • Searching for a specific value within a list of values.
  • The list is in an ascending or descending order.

When we look at the clothing example we see the specific value was to find a jumper that fit perfectly. And we searched through a group of clothes in ascending size.

By having these goals we know that if the found value is smaller than our goal value, we need to look at the larger sizes. But if the found value is too large, we need to look at the smaller ones.

Big O Notation - Logarithmic Notation
Binary Search – Logarithmic Notation

In the example above we accept two inputs:

  • A list of integers we are going to search from ($searchList).
  • The integer we are looking for ($desiredNumber)

Now the code works in the following steps:

  1. Find the total number of items in the list.
  2. Divide that number by 2 and round up, to get the midway point, or just above if the list is an even number.
  3. Check to see if the midway point $midpointList is the number we are looking for. If so stop searching and return the number in text format.
  4. If the midpoint of the list is larger than the desired number, keep only the first half of the list (any number before the midpoint and run the function again with the smaller list).
  5. If the midpoint is smaller than the desired number, keep only the second half of the list (any number after the midpoint and run the function again with the smaller list).

This function uses a technique called recursion to call itself with the smaller list, until the desired number is found.

Linear

A linear notation is the third most efficient notation.

This notation can be identified when the amount of time/space required to process an input grows at a fixed rate, as the input grows.

If a linear algorithm takes one second to process an input of one. It will take ten seconds to process an input of ten.

Every time the input grows by one, the processing time increases by one second.

If we can guarantee this in the code we can say the algorithm is linear.

Real Life Scenario – Clothes Shop

If we go back to the clothes shop example with Jen.

She is looking to buy a jumper. There are nine different sizes and she is not sure what her size is.

Rather than using divide and conquer like she did in the logarithmic example, she would like to try every size on to see which jumper fits the best.

Every jumper takes two minutes to try on and she will make her decision after trying on every size.

If there was just one size of jumper it would take her two minutes, but as there are nine different sizes, it will take her eighteen minutes.

Jen knows this beforehand as the time taken to try on the jumper is the same for every size – it is a fixed rate.

2 minutes x Number of sizes.

If the store increases the number of sizes in the store, that amount of time to find the correct size grows.

PHP Example

A typical example of a linear function is a single for loop which is dependent on an input:

Big O Notation - Linear Function
Linear Function

In the example above we have a for loop that will loop through the echo statement (used to print text), and print out the text a specific number of times. This number is dependent on the input $jumperSizes, and will stop looping once the counter $i is no longer less than the input.

Here is an example of how many times the text will be printed dependent on the input:

Big O Notation - Linear output

Can you tell how many times the line of text will be printed if the input is 100?

It’s easy to tell as the number of times the text is printed increases by one, every time the input increases by one.

A linear notation is efficient as it scales at a fixed rate of the input.

Aim to use these Big O Notations

We have just covered the three most efficient notations for Software Engineering.

Using algorithms will ensure your code is scalable to a high rate. But with any enterprise system, you will not be able to limit all your algorithms to one for loop or constants, due to their limited use cases.

For the next article, we will help you understand the next three most efficient algorithms: n log n, Quadratic and Cubic notations.