DSA Concept: Asymptotic Notation, Calculating order in terms of Input Size| DSA Tutorial #2

 DSA Concept: Asymptotic Notation, Calculating order in terms of Input Size| DSA Tutorial #2

Calculating Order in term Of Input Size

In Order to Calculate the order, most impactful term containing n(Size of Input) is taken into account. Let us assume that the formula of an algorithm in terms of input size n Looks Like this:-

Algo 1- k1n²+k2n+36

                   Algo 1- k1n²+                                  k2n+36

                        ⬆️                                    ⬆️

                                        (Higher Order Term)               (Can Ingore lower order Terms=>On²)

Algo 2- k1R2²+k3k2+8

Note that these are the formulas for the time taken by them.

Asymptotic Notations

Asymptotic Notations gives us an idea abput how good a agiven algorithm is campared to another algorithm. Lets us see the methematical definations of the "order of" now.

Primarily there are three types of widely used asymptotic notaions:

• Big Oh Notiations(O)
• Big Omega Notation(Ω)
• Big Thetha Notation(θ)

Lets Understand it One By One:-

1. Big Oh Notations

Big Oh Notations is used to descirbe asymptotic upper bound, Methametically, if f(n) describes running time of an aglorithm; f(n) is O(g(n)) iff there exist postive constant C(Constant) and a Number Such that 

O≤f(n)≤cg(n)   for all n(This n is used to give upper bound function)≥N,  if a Function is O(n), it automatically O(n²).

==> Graphical Representation 

2. Big Thetha Notation 

Let f(n) define running time of an algorithm, f(n) is said to be θ(gn) if f(n) is O(g(λ)) and f(n) is Ω(g(x)).

Matheatically,

O≤f(x)≤C1g(n)∀n≥n0

O≤C2g(n)≤f(x)∀n≥n0

Merging both the Equantions, we get:

O≤C2g(n)≤f(x)C1g(n)≥n0∀n²

The Eqautions Simply means there exist positive constansts C1 and C2 such that f(x) is Sandwitched Between C2g(n) and C1g(n).

==> Graphical Reperesentation of Big thetha

Now There Questions arrive which one of these two to use?

Since Big Thetha Gives a Better pciture of runtime for a given algorithm, n most of the interveiwer expects you to provide and answer in terms of Big Thehta When they Say "order of".

Quick Quiz: Prove that n²+n+1 is O(n³),Ω(n²) and θ(n²) using Respective Definations.

Increasing Order of Common Runtimes

1<logn<n<nlog<n<n²<n³<z²<n

This is how we can learn and Understand Asymptotic Notations, The Rime time 1 is the Best Case for any Algorithm and nlogn is common runtimes from better to worse and the Last n is the worst cast that can be seen in any algorithm. There will we More Tutorial which will be uploaded to this wesbsite so stay Connected.