## Introduction

Big O notation is a tool used by software engineers to check how efficient an algorithm is. If you haven’t heard or studied about the Big O notation before, the name might sound a bit scaring. However, the concept itself is simple enough even for everyone to understand. Even those who are just getting started on the field.

Yes, there will be times (algorithms) that will be not-that-easy to analyze, but most of the time, you will be able to identify an algorithms complexity very fast. Read on and learn how the Big O notation works. I hope you enjoy the content.

## What is Big O Notation?

Big O notation is a way to express the worst case scenario of an algorithm’s time or space complexity. In simpler terms, it helps you answer the following question:

As the size of my input grows, how does that affect my algorithm’s performance?

**Time complexity** with Big O notation is all about how much *time* the algorithm takes to run in relation to the input used with it. Often represented as `n`

, time in this context does not refer minutes, seconds and the like, but rather the number of operations an algorithm needs to perform.

**Space complexity**, on the other hand, is about how much *space* (or more specifically memory) the algorithm needs process an input.

If you understand the Big O notation, you will be able to predict and talk about how an algorithm will scale. From time to time, dependending on the area of software development that you work on, you will need to apply this knowledge to write (or improve) some algorithm that deals with a large amount of data.

## Understanding Different Big O Notations

### O(1) - Constant Time

The first time complexity you will learn about is called “O(1) Constant Time”. This one is super easy to understand and also the most efficient one. O(1) represents a constant time complexity where, no matter the size of the input, you will always finish the computation in just one operation.

That is, an algorithm is said to have a constant time complexity when the time taken for it to complete its process does not change with the size or complexity of the input data set. A classic example of this is accessing an element from an array by its index. Regardless of the size of the array, it takes the same amount of time to retrieve an item because you’re directly accessing it by its exact address in memory.

The code snippet below shows an example of an algorithm with a contant time complexity:

1 | function getItemAtIndex(array, index) { |

In the code snippet above, you can see a function called `getItemAtIndex`

(by the way, this function exists for illustration purposes only, as it is quite useless to create a function like that) that receives two parameters: `array`

and `index`

. Then you can see that the function returns an item from the `array`

based on the `index`

parameter.

If you were to play with this example, you would see that you could change the `array`

you are passing to `getItemAtIndex`

and add thousands and thousands of items, and the function itself (the algorithm) would be as efficient as it is when you have just 10 items. That is, the time needed for the algorithm to complete its process is constant.

The graph below shows the input size growing (x axis) while the time complexity staying at 1 all the time.

### O(n) - Linear Time

The O(n) notation represents linear time complexity. This notation refers to an algorithm where the time complexity grows along with the size of the input data. That is, if you double the size of the input, the time complexity will roughly double as well.

As an example, check the following code snippet:

1 | function findValue(array, value) { |

As you can see, `findValue`

function (the algorithm you will examine), gets an `array`

and tries to find the position (the index) of a `value`

inside this array. So, this algorithm is considered to have an O(n) linear time complexity because, if the size of the `array`

parameter grows, finding the requested value will take longer and longer.

Sure, if, by chance, the function is called with an `array`

with a million elements and a `value`

that is on the very first position, the algorithm will end up instantaneously. However, what you have to remember is that the Big O notation is about the worst case scenario. That is, on the scenario described here, you have to consider what would happen if you end up calling `findValue`

with a `value`

that is on the far end of the `array`

.

The following graph represents the Big O notation for “O(n) - Linear Time” algorithms. You can see on this graph that, if the input size is `4`

, `4`

will be the time complexity; if the size is `7`

, the time complexity will also be `7`

; and so on.

### O(log n) - Logarithmic Time

The O(log n) logarithmic time complexity refers to an algorithm where the time complexity increases logarithmically in relation to the size of the input data set. That is, an algorithm of that complexity is expected to perform better than an algorithm that grows linearly (the O(n) above).

One of the most popular examples of an algorithm that is O(log n) is the binary search one. If you don’t know the binary search algorithm, take a look at the following code snippet:

1 | function binarySearch(array, value) { |

What you see above is an algorithm that is parsing a sorted array (note, the array used with the binary search must be sorted for it to work) in search for an element. The function above has the same goal of the `findValue`

on the previous section (“O(n) - Linear Time”), however, the difference is that instead of checking one element after the other, the `binarySearch`

algorithm jumps around. This is what the algorithm does:

- Gets the element in the middle of the array (
`valueInTheMiddleIndex`

). - Compares to the
`value`

being search. - If
`valueInTheMiddleIndex`

and`value`

are equal, return the index. - If
`value`

is smaller than`valueInTheMiddleIndex`

, discard the right side of the`array`

(`end = middleIndex - 1`

). - If
`value`

is greater than`valueInTheMiddleIndex`

, discard the left side of the`array`

(`start = middleIndex + 1`

).

So, for an `array`

(an input) that is sorted, binary search will probably be way faster than the previous example.

The graph below shows how O(log n) logarithmic time algorithms behave when their input grows:

### O(n log n) - Linearithmic Time

### O(n^2) - Quadratic Time

### O(2^n) - Exponential Time

### O(n!) - Factorial Time

## Examples in Code

Use practical examples in a popular programming language (like Python, Java, JavaScript etc.) to demonstrate each time complexity.

## Visualizing Big O Notation

Use graphs to visualize how the different time complexities would perform with an increasing number of inputs.

## How to Calculate Big O?

Briefly discuss how to determine an algorithm’s Big O notation, including rules for calculating Big O and common pitfalls.

## Importance of Big O in Real-world Scenarios

Discuss how understanding Big O impacts the real world. You can provide some real-world scenarios where choosing the right algorithm (based on understanding of Big O) made a huge difference.

## Conclusion

Recap of the importance of understanding Big O notation for any software engineer. Encourage readers to apply this knowledge in their programming practice.

## References and Further Reading

Provide references to any materials or textbooks you quoted or took inspiration from. This might also include suggestions for readers who want to delve deeper.