Question

a) Let T(n) be a running time function defined as T(n) = 3n^2 + 2n + 5, is this ϴ(n^2 )? Explain prove your answer using the definitions of big-o and omega notations.

b) Solve the following recurrence relations using Master theorem.

a. ?(?) = 3? ( ?/3 ) + ?

b. ?(?) = 5?( ?/2 ) + 2?^2

please help them with both

Answer 1

a) Big-O Notation

1. Suppose M is an algorithm and n is the input size. We can see clearly that complexity of a function f(n) of M increases with n increasing.

2.Suppose There is a function f(n) which is bounded by some multiple of g(n) for almost all n. So, There exists a positive integer n0 and a positive number M suct that for all n>n0 we have

f(n) <= M*g(n) , Then we can write f(n)=O(g(n)).

3. Therefore Big-O Notation is used to define Upper Bound g(n) for any function f(n).

Problem Point of View:

Here consider f(n)=3n^2+2n+5 and g(n)=n^2 which is asymptotic Upper bound for f(n).

So, f(n) <= cg(n) , c>0 and n0>=1

3n^2+2n+5 <= cn^2

Assume c=10, therefore 3n^2+2n+5 <= 10n^2

which proves that f(n)=Og(n^2) as Upper Bound.

Omega Notation

1.f(n) = omega(g(n)), iff there exists a postive integer n0 and a positive number M such that f(n) >= Mg(n) for all n>=n0.

2. Omega Notation is Used to find the Lower Bound g(n) for the function f(n).

Problem Point of View:

We Have to always take greatest lower bound.

so, f(n) >= c.g(n) so according to above line greatest lower bound willl always be n^2.

Therefore, 3n^2+2n+5 >= c.n^2 Here we have to choose the value of c carefully. for this expression to hold true. We can assume c to be 1. to make it hold true.

b) Basically Master Theorem is Used for Certain type of problems That satisfies the rule of

T(n) = aT(n/b)+f(n) where a>=1 and b>1.

So Here is Brief Introduction and Solution to This Question.

It is the Introduction of Master Theorem and now here is the solution to the Question.

For a part n.log(n) where base to log function is 2 is the time complexity of the function.

For b part n^2.32 is the Time complexity for the function.

Happy a Happy Coding!!