Big O Notation (worst case)
Tags: dsalgo, onotation
Published: 2022-03-21 13:14:38

To demonstrate complexity, we use Big omega(Ω), Big Oh(O), Big theta(θ).

Big Oh(O) represents the worst case. Let's learn some of the basics for Big O notation.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tenelgde6mm2dsje4yj6.png)


**_O(n)_**
If a loop works for n times, the complexity is O(n)

```
#O(n)
def print_item(n):
    for i in range(n):
        print(i)

print_item(10)
```
Graph for O(n)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nog4d76t0rrc0w2ooyos.png)

**_O(n^2)_**
If there is a loop within a loop, it is generally O(n^2). But here is a thing . O(n^3), O(n^100) or anything where n has more value than 2 , we will use n^2. 

```
#O(n^2)
def print_item(n):
    for i in range(n):
        for j in range(n):
            print(i,j)
        
print_item(10)

print('#Another example')
def print_another(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i,j,k)

                    
print_another(10)
#This belongs to O(n^3) but what ever multiples by n, we will just use O(n^2).

```
Graph for O(n^2)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uu6xvnjltbmu9ybo2pau.png)


**_O(1)_**
If there is just one operation, we will have O(1).

```
#adding 2 numbers but just one simple summation . so , 1 operation
#O(1)
def add_items(n):
     return print(n+n)
add_items(10) 

#Summing 3 numbers but again it is one summation ; so 1 operation
#O(1)

def add_items1(n):
     return print(n+n+n)

add_items1(10)    
```
Graph for O(1)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dx3otf9oupxhkeiez142.png)

**_Drop Non dominants_**
If there is a less powerful complexity, we can drop that. For example, if we have O(n^2) and O(n) in a code, we can write it as O(n^2 + n) == O(n^2)

```
def print_item(n):
    #O(n^2)
    for i in range(n):
        for j in range(n):
            print(i,j)
    
    #O(n)
    for k in range(n):
        print(k)        
        
print_item(10)


#So, totally O(n^2 + n). But it will be O(n^2)   
```
**_Drop Constant_**
We will ignore the constant on Big O notation.
```
def print_item(n):
    for i in range(n):
        print(i)

    for j in range(n):
        print(j)

print_item(10)

#here we have O(2n) but we will call it  O(n).
```
here we have O(2n) and we won't write it as 2n. Rather as n.


**_O(log n)_**
Assume that you have a sorted list of 8 numbers. Starting from 1,2,3,........8. You need to find 1.
So, you can use divide and conquer and first make 2 portion. First portion has 1,2,3,4 and second one has 5,6,7,8. Your desired number is on 1st portion and thus you will move to 1,2,3,4. now divide it to 2 portion and one has 1,2 and another has 3,4 . Remove 3,4 and now you will have 1,2. Now divide 1,2 and you have 1 and 2. You have got your desired 1. so , it took 3 steps or 3 equal distribution of 8 numbers to get your desired number.
Now, see that 2^3=8 . right? Which is like  log2 8=3 . right? Thus it is log n notation.

Graph for O(log n)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4udb896lqufe5yt2wchw.png)



Check out this website to know about the complexity of certain algorithms: 
https://www.bigocheatsheet.com/


Array Sorting Algorithms
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5oxrjzfwr8vlwwqz2rul.png)

Common Data Structure Operations
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ko7xj6a6zztg7bmhl360.png)