Execution time of an algorithm on faster computer?

Question

An algorithm takes 1 second to execute a dataset of size N on a particular computer. Replace it with a computer that is 10 times faster. What will be the size of the dataset you can process in 1 second on the new computer if the execution time for a dataset of size n is proportional to n^2?

I am having a hard time wrapping my head around this question. I think that if the machine is 10 times faster, it should be able to execute 10 times the amount of data. This means it could do a data set of size 10N. But wouldn't this only be if the execution time was proportional to n? If the execution time grows quadratic as the input grows, wouldn't the dataset have to be less than 10N?

Answer 1

Well theta-O complexity can thought of as how many discrete operations must be performed to reach the final state. So if it has O(n^2) complexity then it performs at most n^2 operations. Complexity has nothing to do with the speed itself of the computer. In fact it is only loosely related to computation speed. It just means how much work the computer has to do to reach the result.

The speed of a computer has to do with how many discrete operations it can perform per second. Since you want to know what N you would select to perform 10 discrete operations, try asking, "what N would increase the overall number of operations by 10?" the answer would be the square root of 10.