Assume that, a certain algorithm with the running time n^3 uses 100 sec to solve
ID: 3791121 • Letter: A
Question
Assume that, a certain algorithm with the running time n^3 uses 100 sec to solve an instance of size 10^3 on a computer A. This algorithm was improved and now has the running time O(n^2). In the meantime, we acquired a faster computer B, that is about 20 times faster than computer A. How long will it take this improved algorithm to solve an instance of size n = 10^4 on the computer B? Choose the closest estimate. 1 sec 33 sec 120 sec or more 13 sec 68 sec not listed The purpose of performance profiling is to measure program performance. One part of your PA1 assignment asked to measure performance of your d-smooth algorithm to verify if the running time of the program corresponds to the desired O(n log n). Assume that you have performed an experimental analysis of an algorithm, and profiling returned the following times: for instances of sizes 2^10, 2^11, 2^12, 2^13, 2^14 the corresponding times are approximately 300, 500, 1100, 2900, 81200 milliseconds. There is an extra overhead resulting from clocking program performance and functions calls, and this overhead has to be considered in analyzing data. That is, the measured time consists of two components: the time for executing the operations, plus the overhead from profiling. The estimated overhead due to profiling is about 200 milliseconds independently of the input size, (that is, 200 is always an additive "constant"). Based on these experimental results, what is the running time for executing operations in this algorithm? (c is a constant) In particular, is your implementation running in O(n log n)? c middot log n c middot n c middot n log n c middot n Squareroot n c middot n^2Explanation / Answer
1. 1 sec, The closest answer to 0.5 secon is 1 second.
100 sec is taken in n3 time algorithm with n=103 so total instructions =(103)3=109
Let's calculate time taken per instruction=100/109=10-7
Now new algorithm is 20 times faster, it means it will take 10-7/20 time to execute. Now n=104 with O(n2) it will take (104)2=108
Total time taken=108*10-7/20=0.5 Seconds
2. E. n2 is the answer. For come constant value of c O(n2)is the runni g time of the algorithm.