Big O Notation (worst case)

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.

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)

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)

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)

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)

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

Array Sorting Algorithms

Common Data Structure Operations