How Much Faster Can You Get?

Computer Science Level 2

Running a process on a computer with \(n\)-processors does not necessarily reduce the runtime by \(n\) folds. Let's try to see how bad this can be at times.

Chris bought a house with 10 rooms: 9 of them are of the same size and the \(10^\text{th}\) one is double that size.

Let's say that the time Chris takes to complete painting the entire house all by himself is \(a\) units.

Chris realises that \(a\) units is pretty long and invites 9 friends over, who work at the same rate as him. (To clarify, we have 10 people working now).

Let's further say that the time all these people take to complete painting the entire house if they are working together simultaneously is \(b\) units.

Find the ratio \( \dfrac ab\).

Clarification: The walls are being painted with complex patterns. Not more than one person can work on painting the same room at a time since it is hard for them to coordinate.

This problem was inspired by The Art of Multiprocessor Programing.

Problem Loading...

Note Loading...

Set Loading...