Given an algorithm whose worstcase running time is fn 2n ie

Given an algorithm whose worst-case running time is f(n) = 2^n (ie 2 raised to the nth power), and given that the amount of data is n = 1,000. How long would it take this algorithm to complete, assuming that each primitive operation require 1 nano-second (i.e., 1 billionth of a second) to execute. Show your work. Give you answer in a readable form (ie, don\'t say 86,000 seconds, say instead \"1 day\") Given an algorithm whose worst-case running time is f(n) = n, determine the largest possible value of n such that the algorithm will run within time t = 1 second. Assume that each primitive operation requires 1 micro-second (ie., 1 millionth of a second) to execute. Show your work.

Solution

Q11.) For n = 1000, 2 ^n = 2^1000 instructions

time taken by each instruction = 1 * 10^-9 sec

so, total time taken is 2¹⁰⁰⁰ * 10^-9 = 1.071509e+292 sec = 1.24e+278 days.

Q12.) Time taken to execute one instruction = 10^-6 sec

No. of instructions can be executed in 1 second = 1/10^-6 = 10⁶

since f(n) = n. Therefore, maximum value for n can be 10⁶.

Hope it helps. Do give your feedback.