Either you can download the notes in pdf (Link is at the end of the page) or you can read them on this site itself.
Asymptotic notation gives us an idea about how good a given algorithm is compared to some other algorithm.
Let us see the mathematical definition of “order of” now,
Primarily there are three types of widely used asymptotic notations.
Big oh notation ( O )
Big oh notation is used to describe asymptotic upper bound.
Mathematically, if f(n) describes running time of an algorithm; f(n) is O(g(n)) if there exist positive constants C and n_{o }such that,
O ≤ f(n) ≤ c g(n) for all n ≥ n_{o} [It is used to give upper bound on a function]
If a function is O(n), it is automatically O(n^{2}) as well!
Graphic example for Big oh ( O ):
Big Omega Notation ( Ω )
Just like O notation provides an asymptotic upper bound, Ω notation provides asymptotic lower bound. Let f(n) define the running time of an algorithm;
F(x) is said to be Ω (gx) if there exist positive constants C and n_{o }such that,
O ≤ c g(x) ≤ f(x) for all n ≥ n_{o} (used to give lower bound on a function)
If a function is Ω (n^{2}) it is automatically Ω (n) as well.
Graphic example for Big Omega (Ω)
Big theta notation ( θ )
Let f(x) define running time of an algorithm
F(x) is said to be θ (gx) if f(x) is O (g(x)) and f(x) is Ω (g(x)).
Mathematically,
The equation simply means there exist positive constants C_{1 }and C_{2 }such that f(x) is sandwiched between C_{2 }g(x) and C_{1 }g(x).
Graphic example of Big theta ( θ )
Which one of these to use?
Since Big theta gives a better picture of run time for a given algorithm, most of the interviewers expect you to provide an answer in terms of Big theta when they say “order of”.
Quick Quiz: Prove that n^{2}+n+1 is O(n^{3}), Ω(n^{2}), and θ(n^{2}) using respective definitions.
Increasing order of common runtimes
You can download the notes by simply clicking on this below download link. :)
Sir I want to ask Machine Learning ki playlist me complete course h ya abhi kuch chize bachi h aur kya wo sb in future cover kroge aap
Any Course related announcements will be posted here