If an algorithm with time complexity N takes one day to treat some data, how long would an algorithm-CodePudding

I can't get my head around how to answer this question, I do know how to find time complexity, but just can't make sense of this.

CodePudding user response：

Time complexity expresses a relation between the rate of change of the input data and the time it takes to process the data for a particular algorithm.

This means that while algorithm A with linear time complexity may take 1 day to complete processing n == 1000, algorithm B, also with linear time complexity, may take one week to complete processing the same data, quantity and quality wise. But when you know that algorithm A is linear and takes 1 day to complete n == 1000, you know that it takes roughly 10 days for A to complete n == 10000.

Now, you know that some algorithm with linear complexity takes one day. You are given a completely different algorithm (we must assume it is different because the time complexity is totally different) with complexity n log n, and are asked to guess how long it takes? You cannot know. You don't know the constants that are in play. So it would be wrong to make assumptions based on a linear algorithm that you have tested.

If you want to guess the time a linearithmic algorithm takes, you need to test that algorithm and make assumptions based on tests that you made on that algorithm. That's because, and I want to emphasize that, time complexity expresses a relation between the rate of change of the quantity of the input data and the time it takes for an algorithm to finish. The relation is between this specific algorithm's times and its input.

CodePudding user response：

Let m be the length of the data. The O(N) algorithm takes C times m = 1 day to treat the data; C being a constant equal 1 day / m in this case.

Now the O(log N) algorithm should take C times log m to treat the data. However, the constant C in this case is not necessarily equal to the constant C in the first case.

Therefore, you can't tell how much the O log N algorithm will take to treat the same data. It could be less, equal or more time. However, the larger the data the better the second algorithm will perform.