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

The new time complexity for each algorithm on a machine that is 64 times faster can be calculated by dividing the original time complexity by 64. Without the value of 'T', we cannot solve for specific values of 'n'. For the bonus question, calculating the sorting time involves using the instruction rates and algorithm complexities.

Step-by-step explanation:

For algorithms with time complexities of T(n) = 10 ∙ 2^n, T(n) = 5 ∙ n^3, and T(n) = 16n, and given that a new machine is 64 times faster, the goal is to find out how many inputs (n) can be processed in the same time T as before.

The new time complexity for each algorithm with the faster machine would simply be the original time complexity divided by 64. So for the first case, it's T(n) = (10 ∙ 2^n) / 64, for the second, it's T(n) = (5 ∙ n^3) / 64, and for the third, it's T(n) = (16n) / 64, which simplifies to T(n) = n/4. To solve for n, we'd set these equal to T for each and solve respectively, but as we lack the actual value of T, we cannot provide specific numerical answers.

For the bonus problem, we use the given instruction rates and calculate the time for computer A and computer B to sort 10 million numbers with respective complexities of 2 ∙ n^2 and 5 ∙ n ∙ log2(n). With a calculation, we could determine the actual sorting time for both, in seconds, considering computer A's instruction rate of 1 billion per second, and computer B's rate of 10 million per second.

Answer 2

a. m = 64n

b. m = 4n

c. m = 64n

Step-by-step 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