Question

Time complexity: Be sure to show your work. Suppose that a particular algorithm has time complexity T (n) = 10 ∗ 2n, and that execution of the algorithm on a particular machine takes T seconds for n inputs. Now, suppose you are presented with a machine that is 64 times as fast as your current machine. How many inputs can you process on you new machine in T seconds?Suppose that a particular algorithm has time complexity T (n) = 5 ∗ n3, and that execution of the algorithm on a particular machine takes T seconds for n inputs. Now, suppose you are presented with a machine that is 64 times as fast as your current machine. How many inputs can you process on your new machine in T seconds?Suppose that a particular algorithm has time complexity T (n) = 16n, and that execution of the algorithm on a particular machine takes T seconds for n inputs. Now, suppose you are presented with a machine that is 64 times as fast as your current machine. How many inputs can you process on you new machine in T seconds?Bonus:Suppose that computer A executes 1 billion instructions per second, and computer B executes 10 million instructions per second, i.e, Computer A is 100 times faster than computer B in raw computing power. Suppose an expert programmer implements insertion sort in machine language for computer A, and the resulting code requires 2 * n2 instructions to sort n numbers. Suppose an average programmer implements merge sort, using a high-level language on computer B, with the resulting code taking 5 * n *log2n instruction. How long does computer A and computer B take to sort 10 million numbers respectively?

Answer 1

Answer:

a. m = 64n

b. m = 4n

c. m = 64n

Explanation:

a) Time complexity in this problem is,

T(n)10 x 2n

For n inputs the old machine takes T seconds,

The new machine is 64 times faster than current machine. Suppose it solves m operation in same time then,

T(m)/T(n) = 64

20m/20n = 64

m = 64n

so it will solve 64n inputs in T Time.

b) Same as above problem, we get,

T(m)/ T(n)= 64

5m^3/5n^3= 64

m^3n^3 =64

m^3 = 64n^3

m = 4n

c) The no of inputs that can be solved on 64 times faster machine is,

T(m)/T(n) = 64

16m/16n = 64

m/n =64

m=64n