Please solve part C Suppose that a particular algorithm has time complexity T(n)

Question

Please solve part C

Suppose that a particular algorithm has time complexity T(n) - 3 times 2^n, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds? Suppose that another algorithm has time complexity T(n) - n^2, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds? A third algorithm has time complexity T(n) - 8n. Executing an implementation of it on a particular machine takes t seconds for n inputs. Given a new machine that is 64 times as fast, how many inputs could we process in t seconds?

Explanation / Answer

c)

We have T(n) = 8n in the older machine, and
We want to know for what value of n = n1 will we have Tnew(n1) = T(n) Using our formulas, we have.

But new machine 64 times faster than old machine .
So , => 8n = 8n1 / 64

=> n1 = 64 n

So we can solve a problem 64 times larger on the new machine.


Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---