1

Suppose that an algorithm uses $2n^2+3^n$ bit operations to solve a problem of size $n$. Suppose that your machine can perform one bit operation in $10^{-9}$ seconds, how long does it take your algorithm to solve a problem of size given below. Note, if your algorithm takes more than $60$ seconds, answer in minutes. For more than $60$ minutes, answer in hours. For more than $24$ hours, answer in days. For more than $365$ days, answer in years. For more than 100 years, answer in centuries!

(a) 10

(b) 20

(c) 50

(d) 100

(e) 1000

1 Answers1

1

We deal with $n=50$. So we need to evaluate $2(50)^2+3^{50}$. The $2(50)^2$ part is easy to evaluate, by calculator, or, more simply, in one's head. We get $5000$.

Actually, it doesn't matter what we get, since $2(50)^2$ is utterly negligible in comparison with $3^{50}$.

To evaluate $3^{50}$, we can use a calculator. But because your calculator may later choke on $3^{1000}$, we do it another way.

We will use logarithms to the base $10$. So by $\log$ we mean $\log$ to the base $10$. Note that $3=10^{\log 3}$, so $3^{50}=10^{50\log 3}$.

The calculator gives $50\log 3\approx 23.856$, so $3^{50}\approx (10^{23})(10^{0.856})$. We conclude that $$3^{50}\approx 7.18\times 10^{23}.$$ Each operation takes $10^{-9}$ seconds. So the number of seconds used is approximately $7.18\times 10^{14}$.

Divide by $3600$ to get hours, then by $24$ to get days, then by $365$ to get (roughly) years, then by $100$ to get centuries. A long long time! The point of the problem is to give your calculator some exercise, and to show you how fast the function $3^n$ grows.

Remark: Actually, we don't absolutely need logs to calculate $3^{1000}$. My cheap scientific calculator says "E" and refuses to do anything if I tell it to find $3^{1000}$. However, it has no trouble declaring that $3^{125}\approx 4.3667\times 10^{59}$. But $3^{1000}$ is the $8$-th power of this, which is about $(4.3667)^8\times 10^{(8)(59)}$.

André Nicolas
  • 507,029
  • Thanks man, I'm assuming that is section c) Where did you get 10^14 AND 10^-9 from? – Patamara Mar 23 '13 at 17:51
  • It says in the problem that one operation takes $10^{-9}$ seconds. So to get the time in seconds, we multiply the number of ops needed, which is about $7.18\times 10^{23}$, by $10^{-9}$. Finally, note that $19^{23}\times 10^{-9}=10^{23-9}=10^{14}$. – André Nicolas Mar 23 '13 at 17:56
  • You are the best! Thanks a lot – Patamara Mar 23 '13 at 18:01