How does processing speed affect algorithm performance?

Question

I'm currently taking a class on algorithms, and we are studying algorithmic efficiency. I understand classifying algorithms based on their time complexity, but I am confused about the following category of questions:

Suppose algorithm A has time complexity C (C being along the lines of n^2, n + 1, 3 * 2^n, etc.), and it takes t seconds to execute A on a given machine for a certain number of inputs n. If you execute A on a machine that is M times faster than the original machine, how many inputs (n) can be processed in t seconds (same number of seconds as on the previous machine)?

I know that the greater the time complexity of an algorithm, the less improvement is gained by speeding up the machine, however I can't seem to figure out a reliable equation to compute the new number of inputs. For algorithms with linear time complexity, I think I am correct with: multiply the time complexity (constant * n) times the increase in speed to get M * constant * n. I haven't found much information about this either in books or elsewhere on the web; if anyone can help me create a better equation it would be much appreciated!

Answer 1

Let's say that the execution time of an algorithm is $\Theta(f(n))$. That means the execution time is between c·f(n) and C·f(n) for all n ≥ N, for some N, c and C. Because of the constant, you can't say anything definite about the maximum problem size that can be solved in time T on a slow and a fast computer.

You can assume that the actual execution time is c·f(n) for a c that you know; that assumption is neither completely unreasonable nor completely justified. Then define for example n' as the value where c·f(n') = k · c·f(n), to get something meaningful for a machine that is k times faster.

Calculating n' depends on the nature of f(n). If f(n) is linear, then n' = k·n. If f(n) is cubic, then n' = $k^{1/3}·n$. If f(n) = c·n·ln n then n' is a bit less than k·n, the exact result is difficult. If f(n)=$2^n$, then n' = $n + \log k$. The last shows why efficient algorithms don't become less important with faster computers in practice: Because the less efficient the algorithm, the less a faster computer can improve the size of a problem that can be solved in fixed time.

Answer 2

Okay so I think I might have just answered my own question. I am not completely sure this is accurate, so feel free to correct me.

If computer 1 can compute m operations in t seconds, and computer 2 is x times faster than computer 1, then computer 2 can compute xm operations in t seconds.

For an algorithm with linear time complexity, each input n requires some constant a times n operations. To get the number of inputs a faster computer could handle in time t, simply multiply x times m, and then multiply that by your constant a.

For algorithms with greater time complexity, you still continue to multiply m operations by x times faster. However, you also have to account for the fact that m operations does not directly translate into n outputs in a linear way. If the time complexity is n^2, then xm operations only gets you sqrt(x) more outputs in time t.

Update: I'm now not at all sure this is correct, if anyone knows more about this, feel free to chime in.

Answer 3

When considering different clock speeds, the same equipment might be "computer 1" for a few seconds, with power saving 1 GHz clock rate, and then might become "computer 2" for a few seconds, clocked at its max of 2 GHz.

You consider that "computer 1 can compute m operations in t seconds". But there are several "operations". Consider the "add one to an array" algorithm:

for (i = 0; i < N; i++) {
    a[i]++;
}

Computing effective address within the array may happen quickly, in a single clock cycle, and be strongly dependent on the core's clock rate. Reading a value from the array often takes multiple clock cycles, and will be influenced by prefetcher and state of each cache level. Above we see one of two sequential permutations of array indexes, but any permutation would work, though some permutations will interact badly with prefetch and with cache lines. Changing a core's clock rate typically doesn't alter memory bus timings. Disk I/O, e.g. for page faults, is even further down the memory hierarchy. Pipelines and other overlap of work will additionally muddy the waters.

You spoke of the time it takes for a computer to perform "an operation", but you probably want to speak of the time needed for each of several operations. In practice, a small number of them will dominate so a simplified analysis can focus just on those.