1 For the following questions select a theta notation and ju

1. For the following questions select a theta notation and justify (meaning show it is Big-Oh and BigOmega
of your selected theta).
(a) 6n + 1
(b) 3n + 2*n lg n
(c) (n+1)(n+3)/(n+2)
(d) 2 + 4 + 8 + 16 + · · · + 2ⁿ (Note: for this one you may need to prove that this sum
satisfies a specific equation first.)

Solution

(a) 6n + 1 will belong to bigoh(n)

6n + 1 <=7n, for n>=1

Hence the (6n+1) = O(n)

Similarly, 6n + 1 = BigOmega(n)

Hence it will be Theta(n)

(b) Growth rate of nlogn > n

Hence the theta(n log n)

(c) (n+1)(n+3)/(n+2)

It will be theta(n)

(d) 2 + 4 + 6 + 8 + ... + 2n

=> 2n(n+1)/2

=> n^2 + n

Hence it will be Theta(n^2)