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.
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)
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).
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)
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)
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.
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.
Check out this website to know about the complexity of certain algorithms:
Top comments (0)