Question

Give the formal definition of Big-O, Big-Omega, Big-Theta, and little-O and then describe them in your own words

Answer 1

Big-O:This tells the largest amount of time taken by the program to complete its execution.

f(n)<=c*g(n) then it is represented as f(n)=O(g(n))

here c is constant.

Big-Omega:This tells the least amount of time taken by the program to complete its execution.

f(n)>=c*g(n) then it is represented as f(n)=OMEGA(g(n))

here c is constant.

Big-Theta,​​​:This tells the average amount of time taken by the program to complete its execution.

c1*g(n)<=f(n)<=c2*g(n) then it is represented as f(n)=THETA(g(n))

here c1,c2 are constants.

little-O:

if f(n)<c*g(n) then it is represented as f(n)=o(g(n))

here c is constant.