News for hackers. Stuff that matters.
Re:A hash table by any other name by stoperaticless on Friday August 02, 2024 @05:51PM (#41142978)
Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) < C x g(n), when n goes to infinity.

Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation/shuffle has different exec time), parameter “permutation” can not go to infinity, so it can’t be used with O(n) directly. (Parameter need to be single real number)

QuickSortWorstCaseTime(n) is single valued function thus, it can be used with O(n) notation. Same is true for quickSortAvgCaseTime(n) and quickSortBestCaseTime(n).

But you answered my question. (Very indirect “Yes” :) )

Re:A hash table by any other name by lkirkwood on Tuesday August 06, 2024 @08:53PM (#41177149)
It's true that in the case of a sorting algorithm it's not immediately obvious how to analyse the time complexity with Big O. However, I feel that you may be getting bogged down in semantics.

Perhaps it is accurate to say that when Big O is used to describe the time complexity of a function in computer science the variable n in O(f(n)) usually describes the size of the input, which may not be common knowledge. But if the question is:

> Have programmers redefined O to specifically mean worst case?

Then in general I would say no. I suppose to answer more concretely I would have to ask: "Which programmers?"