Growth of Functions

Question 1

An algorithm that is asymptotically efficient is best choice for all inputs?

Answer 1

No, for small inputs the asymptotic efficeiency is not helpful. for small inputs insertion sort o(n^ 2) is faster than merge sort n(logn)

Question 2

what are all the notation used to describe asympototic?

Answer 2

Big-O Notation (O),Omega Notation (Ω),Theta Notation (Θ),Little-o Notation (o),Little-Omega Notation (ω)

Question 3

Big-O notation

Answer 3

Big-O notation describes the upper bound of an algorithm’s growth rate. It gives the worst-case time or space complexity.

Mathematical Representation:
f(n)=O(g(n)) if there exist constants
c>0 and 𝑛0≥0
such that:

f(n)≤c⋅g(n),foralln≥n0
​
.

Question 4

Omega Notation (Ω)

Answer 4

Omega notation describes the lower bound of an algorithm’s growth rate. It gives the best-case time or space complexity.

Mathematical Representation:
f(n)=Ω(g(n)) if there exist constants
c>0 and 𝑛0≥0
such that:

f(n) ≥ c⋅g(n),foralln≥n0
​

Question 5

Theta Notation (Θ)

Answer 5

Theta notation describes the tight bound of an algorithm’s growth rate. It bounds the algorithm from above and below, describing its exact asymptotic behavior.

Mathematical Representation:
f(n)=Θ(g(n)) if there exist constants
c1,c2>0 and n0≥0

c 1. g(n)≤f(n)≤c2 ⋅g(n),
foralln≥n 0
​
.

Question 6

Can we use all notation to specify running times?

Answer 6

Yes, but we need to mention precisely is good practice. for example we can say worst case running time of insertion sort in Big O(n^2), Omega(n^2),Theta(n^2), but Theta is most suited since running time is tightly bounded

Question 6

Little O

Answer 6

it refer to running is stricly lower than inputs. Bigoh means is equal to or slower.

Question 7

ω (Little-Omega)

Answer 7

strictyl faster than inputs,
Big omega is atleast it will run for the inputs