I am undertaking the algorithms course on Coursera, there is a section where the author mentions the following
the running time of weighted quick union with path compression is going be linear in the real world and actually could be improved to even a more interesting function called the Ackermann function, which is even more slowly growing than lg. And another point about this is it seems that this is so close to being linear that is time proportional to N instead of time proportional to N times the slowly growing function in N. Is there a simple algorithm that is linear? And people, looked for a long time for that, and actually it works out to be the case that we can prove that there is no such algorithm. (emphasis added)
(You can find the entire transcript here)
In all other sources including Wikipedia "linear" is used when time increases proportionally with the input size, and in weighted quick-union with path compression this is certainly not the case.
What exactly is meant by "linear in the real world" here?
Here are some chunks from the transcript:
And what was proved by Hopcroft Ulman and Tarjan was that if you have N objects, any sequence of M union and find operations will touch the array at most a c (N + M lg star N) times. And now, lg N is kind of a funny function....
And another point about this is it< /i> seems that this is so close to being linear that is t ime proportional to N instead of time proportional to N times the slowly growing function in N.
(end quote)
You are pointing out that the cost of an individual operation grows very slowly with the number of objects, but they are looking at how the total cost of a number of operations grows with the number of objects involved so N times a per-operation cost that grows only very slowly with N is still just over linear in N.