Assume that method m is in the complexity class O(N log_2 N), and that for N = 1

Question

Assume that method m is in the complexity class O(N log_2 N), and that for N = 1,000 the program runs in 4 seconds.

(a) write a formula, T(N) that computes the appoximate time that it takes to run m for any inout of size N.
Show your work/calculations by hand, approximating logarithms, finish/simplify all the arithmetic.

(b) Compute how long it will take to run when N = 1,000,000 (which is also written 10^6).
Show your work/calculations by hand, approximating logarithms, finish/simplify all the arithmetic.

Explanation / Answer

Consider the process to compute as single-thread operation.

Then for O(Nlog2N), the running time will be proportional to Nlog2N.

(a)

For N=1000, Nlog2N = 1000 x log2(1000) = 1000 x 9.9657 = 9965.7.
This code runs in 4 seconds, thus the T(N)=k Nlog2N, we have
4 = k 9965.7
=> k = 4.013 x 10-4

Then the formula is T(N) = (4.013 x 10-4 )(Nlog2N)

(b)

Now for N= 106 :

T = (4.013 x 10-4)(106)(log2106)
=> T = (4.013 x 102 )(19.9315)
=> T = 7998.5 seconds

-----------------

Hope this helps.

Kindly rate.

Cheers.

:)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects