This definition from Wikipedia elegantly explains **big-O** in computer science as a classification of algorithms according to how their run time or space requirements grow as the input size grows.

It is an asymptotic analysis which implies that it is input bound. It calculates the worst-case scenario of an algorithm based on input, bounded by time and space.

The calculation for time and space is similar. In this explanation, we calculate the big O notation for time.

We would explain how to identify **O(1)**, **O(log(N))**, **O(N)**, **O(N^2)**. It is worthy to note that the algorithms are arranged in terms of their time performance in the previous sentence.

For example, we calculate the time complexity of 3 algorithms with a given array input below:

```
a = [...] where array size n
We have three algorithms that take
array 'a' as input and returns values.
F1(a) => 1 + a[0];
algorithm F1 returns 1 plus the first
array value of 'a'
F2(a) => sum(a);
algorithm F2 returns the sum of
array value 'a'
F3(a) => pair(a);
algorithm F3 returns the pairing of the
array values in 'a'.
for example if a = [1,2,3], F3 returns
1,2
1,3
2,1
2,3...
```

If the size of the array **'n'** increases

to 10,000,000, we find out that:

F1 algorithm still runs in constant

time as it refers to a pointer to a

memory location like*array[0]*is

**O(1)**F2 algorithm runs in linear time as

the time taken increases proportionally

to the size of 'n' array. The expression

*sum(array)*where array size is an input

that can vary is**O(N)**F3 algorithm would most likely have a

nested for loop that would mean it runs

in**O(N^2)**

## Logarithms in Big O

The expression *log (n) = y* in computer science assumes log is in base 2 and not base 10 like mathematics. This is a very important distinction to make. Therefore the full expression is *log2 (n) = y*.

To get 'n' we simply do **2^y = n**. That means to get 'n' in **log (n)=4**, we simply do **2^4 = 16**.

**How to Identify O(log(N)) algorithms**

Remember that in computer science the expression *log (n) = y* evaluates to *log2 (n) = y*, log is in base 2. Thus an expression **log (n)=4** which can be solved as **2^4 = 16** simply multiplies 2 four times `2*2*2*2`

.

```
If we added 1 to 2^4+1 we would get 16*2 which is
2^5=32
```

**It means that when the input doubles, you only have to do one more operation. The magic happens here!**

To understand if a notation is **O(log(N))**, if we have an algorithm that keeps cutting an array in half like a binary search as shown below:

```
[0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4, | 5,6,7,8,9] => [0,1,2,3,4]
[0,1,2 | ,3,4] => [0,1,2]
[0,1 | ,2] => [0,1]
[0 | 1] => [0]
```

Or if it cuts a tree data structure in half. Read about tree data structure here, it is most likely a **O(log(N))**.

For further studies, visit https://www.algoexpert.io

## Top comments (0)