Question

Assume that algorithm A1's running time roughly equals to T1(n) = 4n^2 + 2n + 6 and algorithm A2's running time roughly equals to T2(n) = 2n lg(n) + 10 . Suppose that Computer A's cpu runs 10^8 instructions/sec. When the input size equals to 10^4, 10^6, and 10^12 respectively, how long will algorithm A1 take to finish for each input size in the WORST case? How long will algorithm A2 take to finish for each input size in the WORST case?

Show all steps and calculations please.

Answer 1

`Hey,

Note: If you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Given CPU has 10^8 instruction/sec

So,

n=10^8 has time 1 sec

So, for n=10^4 for algo A1

1 = 4(10^8)^2 + 2*(10^8) + 6

T = 4(10^4)^2 + 2*(10^4) + 6

So,

T=(4*(10^4)^2 + 2*(10^4) + 6)/(4*(10^8)^2 + 2*(10^8) + 6)

So,

Time taken is ~10^-8 sec

For n=10^6

T=(4*(10^6)^2+2*(10^6)+6)/(4*(10^8)^2+2*(10^8)+6)

T=10^-4 sec

For n=10^12

T=(4*(10^12)^2+2*(10^12)+6)/(4*(10^8)^2+2*(10^8)+6)

T=10^8 sec

For Algo 2

For n=10^4

T=(2*10^4*log(10^4)+10)/(2*10^8*log(10^8)+10)=5*10^-5 sec

For n=10^6

T=(2*10^6*log(10^6)+10)/(2*10^8*log(10^8)+10)=0.0075 sec

For n=10^12

T=(2*10^12*log(10^12)+10)/(2*10^8*log(10^8)+10)=1.5*10^4 sec

Kindly revert for any queries

Thanks.