Moores Law is often stated as The number of transistors on a

Moore\'s Law is often stated as \"The number of transistors on a chip doubles every 2 years.\" This is often restated as \"The speed of computers doubles every 2 years.\"

You\'re given a problem where the theoretical best case algorithm is O(n^4), e.g., a scientific problem on a 3D grid through time.

Explain your answers to the following:

(A) If n = 24,000 and it takes m years to run, how big does m have to be before it makes sense to just wait for a faster chip?

(B) You decide to wait 8 years. In terms of m, how long does the program now take to run on new chips?

(C) At the 16 year mark, how large can you make n in order to match how long it originally took for 24,000 items?

Solution

(a) it takes 2 years to wait for a faster chip.

(b) the program takes 4 years to run on new chips

(c) n should become 4n

therfore 4 x 24000 = 96000