A program takes 35 seconds for input size 20 (i. e., n=20). Ignoring the effect of constants, approximately how much time can the same program be expected to take if the input size is increased to 100 given the following run-time complexities? a. O(N)
b. O(N + log N)
c. O(N^3)
d. O(2^N)1

Given :

To Find :

Expected time for :

a. O(N)

b. O(N + log N)

c. O(N^3)

d. O(2^N)

Solution :

a.

In O(N) relation is ,

t = kn

So ,

35 = k(20)

t = k(100)

t = 175 seconds .

b .

In O( N + log N ) , N is dominating term . So the complexity is simplified in O(N) .

So , t = 175 seconds .

c .

The relation is given by :

So ,

d .

The relation is given by :

So ,

Hence , this is the required solution .