-
Notifications
You must be signed in to change notification settings - Fork 0
/
bigONotation.txt
54 lines (30 loc) · 1.5 KB
/
bigONotation.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Good code has to be both readable and scalable.
Big O termed as Big O Asymptotic Notation.
language used to tell how ong the algoritham takes to finish the takes / how slow it slows down
it should be perfomed with min operations
which function/algorithm/code is best
Rule 1: Worst Case:
Big O only cares about the worst case
Rule 2: Remove Constants
Drop the constants , say if calculations say
O(1+n/2+100) it will be considered as O(n)
O(n)+O(n) i.e. O(2n) it will be considered as O(n)
Rule 3: Different terms of inputs [trickiest]
If our calculation says
O(n) + O(m) then it will be considered as O(n+m)
In case of nested for loop with same array i.e. O(n*n) , will be considered as O(n^2)
Rule 4: Drop Non Dominants
If calculation says
O(n + n^2) then it will be considered as O(n^2)
linear time O(n): no of operations increases as the no of elements increases proportionatly--> where n is no.of elements/inputs
constant time O(1): irrespetive of any numbers of inputs/elements increased its going perform the to task in only one operation
factorial time O(n!) : Most expensive Example : adding /having nested loop for every input
Pillars of Programming:
Redable: clean , maintanable and easily understood
Scalable:
Speed/Time Complexity ( CPU ):
Memory/Space Complexity ( RAM ):
causes : variable , data structures , function call and allocations
Heap: store variables
Stack: function calls
"Premature optimization is the root of all evil"