Question

Can someone help me on this algorithm question?
I don't understand what the problem is asking for...

Suppose a parallel computer system has one thousand processors which are programmed to solve a particular problem in parallel. Derive a reasonable estimate for the largest values of n this computer system can solve in 1 day, 1 month, 1 year, and 10
years, respectively, assuming the algorithms for solving this problem of size n requires O(n), O(n^2), O(n^3) and O(2^n) instructions such that one instruction takes 1 nanoseconds.

Answer 1

question is asking u to calculate how many instructions can be executed

Answer 2

\(1 \ day = 24 \times 60 \times 60 \times 10^9 \ ns\)

Answer 3

I'll solve them for 1 day, you may solve them for the rest


for a problem of size O(n) to finish in 1day, the size cannot be larger than \( 24 \times 60 \times 60 \times 10^9\)

similarly,

for a problem of size O(n^2) to finish in 1day, the size cannot be larger than \( (24 \times 60 \times 60 \times 10^9)^{1/2}\)

for a problem of size O(n^3) to finish in 1day, the size cannot be larger than \( (24 \times 60 \times 60 \times 10^9)^{1/3}\)

for a problem of size O(2^n) to finish in 1day, the size cannot be larger than \( \log_2 (24 \times 60 \times 60 \times 10^9)\)

Answer 4

see if those make some sense :)

Answer 5

yea, thx. i just got it after reading it 30 times over haha.

Answer 6

good :)