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!