Each of the following ten questions has one of the following

Each of the following ten questions has one of the following five answers: theta (1) theta (log n) theta (n) theta (n log n) theta (n^2) n/5 +5/n sigma^n_i=1^3i sigma^n_i=12/I T(n) T(n-1) + 2 log n T(n) = 5T(n/5) + O(n) T(n) = 4T(n/2) + O(n) How many bits are needed to represent the number n^17? Given an unsorted array A of n elements. How long does it take to sort A? Given an unsorted array A of n elements, how long does it take to determine if x epsilon A? Given a sorted array A of n elements, how long does it take to determine if x epsilon A?

Solution

a)

This will be O(n). Correct option is c.

n/5 will run with O(n) and 5/n will also take n. So overall it will take O(n)

b)

it will be O(n).Correct option is c.

it will run with resepct to n for each iteration so O(n)

c)

It is also O(n) as it will run till i reaches n.

Correct option is C.

d)

Here we have two notations one is T(n) other is logn. The next term depends upon previous term plus logn.

So overall running time will be logn.

e)

In this case overall running time will be O(n)

As the term depends on previous value of N plus O(n).

f)

It should also be O(n)

g)

it will be constant always so running time will be O(1)

h)

It will be D. O(nlogn) we can use quick sort.

i)

In unsorted array it will take O(n)

Correct option is C as we need to traverse the whole array to find this.

j)

Correct option is B O(logn).

In case of sorted array we can do binary search (divide and conquer) to find the element in the array.