For each of the following plots, provide a tight big-O bound, a tight big-2 boun

Question

For each of the following plots, provide a tight big-O bound, a tight big-2 bound, and a big-e bound. You do not need to show your work; just list the bounds. If a particular bound doesn't exist for a given plot, briefly explain why. Assume that the plotted functions continue to follow the same trend shown in the plots as increases. Each provided bound must either be a constant or a simple polynomial, from the following possible answers. n2,1,n, logn),n,1/ (a)1o r) 10 15 30 (b) 10 r 15 20 (e)10 ) 10 15 20 25 30 10 15 20 25 10 15 30

Explanation / Answer

First of all i will just clear out the definitions

big theta bound if you write big_theta( g(n) ) it basically contains a whole set of functions f(n) such that

c1*g(n) <= f(n) <= c2*g(n) for all values above some no, here c1, c2 and no are positive constants.

big O bound unlike big_theta bound , it only provides a asymptotic upper bound and not a lower bound, so the following is possible

3n+4=O(n^2) and also 3n+4= O(n) also

big omega bound this one only provides an asymptotic lower bound.

So from the above definitions it is intuitively clear that if a big_theta bound exists then that bound itself is a tight big_O bound and a tight big_omega bound.

or in mathematical terms, f(n) = big_theta( g(n) ) if and only if f(n) = O( g(n) ) and f(n) = big_omega( g(n) ).

So for all your queries below, if i give the answer in terms of big_theta notation, then that automatically qualifies for big_O and big_omega. If big_theta doesn't exist then i will clearly state it.

a) this function can be bound up and below by n^2 , so big_theta(n^2) ( and also big_O and big_omega)

b) although it is an oscillating function, it can be clear bound by by a linear function up and above by suitably choosing the constants, so it is big_theta(n)

c) by the same logic it is big_theta( 1 )

d) big_theta( n )

e) the lower bound(tight) can be a constant and the upper bound(tight) is a linear function. Therefore we do not have a functional bound which can be both upper and lower by (by suitably choosing constants) since the intersection of linear functions and constants is a null set.

big_theta bound does not exist

it is big_O( n ) and big_omega( 1 )

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.