Question

Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular, but unspecified speed in instructions per second). Estimate how long the same algorithm, running on the same hardware, would take if the input contained 230 elements, and that the algorithm's complexity function is: Big theta not Big O

a) Big theta(N)
b) Big theta (log N)

c) Big theta (N log N)

d) Big theta(N^2)

Assume that the low-order terms of the complexity functions are insignificant, and state your answers in the form HH:MM:SS.S (hours, minutes, seconds, tenths of a second). Be sure to show supporting work.

Answer 1

Let's assume that the algorithm had complexity theta(N).

i.e time take for 1 element = 30/224 = 0.133992 seconds.

when we have 230 elements

a) when algorithm has theta(N) complexity the functions grows linearly

==> 230 * 0.133992 = 30.8035 seconds

==> 00:00:30.80

b) when algorithm has theta(log N) complexity functions grows logarithmic

==> log(230) * 0.133992 = 1.051 seconds

==> 00:00:1.05

c) when algorithm has theta (N log N) complexity functions grows linearithmic

==>log(230) * 230 * 0.133992 = 241.6685seconds

==> 00:04:1.6685

d) hen algorithm has theta (N ^ 2) complexity functions grows quadratic

==> 230 * 230 * 0.133992 = 7088.1768 seconds

==> 01:58:08.1768