3 replies to this topic

[xecure]

other then letting the user know the max time it will take for a program to go through a data structure to find the data, what other benefit is there to knowing the worst case speeds for a program?

[Momerath]

Comparing methods to see which is faster. While most of the time you won't deal with really large data sets, some people do (Google, Microsoft, Data mining, etc.) Being able to compare worst case, average case, best case speed can be important.

[WingedPanther]

Real life: I had a database query that was O(n^2) that ran fine on my system, but horribly on the customers 100+GB database. I reworked it as a O(n) query and O(n) logic and the process completed in about an hour.

[zoranh]

In everyday programming, average running time is of more help. However, wost case running time is essential in predicting how long the code will run before producing the output. That is important for every application because you don't want to release a code which runs fine in 1000 tests that you have completed, and then you start receiving one complaint a day saying that it worked horribly long, just because your application is being used a million times a day, which normally produces cases that you haven't generated in your tests.

Worst case running time is essential in serious applications, like running a nuclear plant, or an X-ray device, or navigating a spacecraft. In all such critical designs, worst time is used as running time when analyzing maximum delays produced by the program. Donald Knuth notes this as the reason why hash tables have not gained popularity in serious programming, like space program or health industry - he said that, since worst case running time for hash table is O(n), it could never be used in those applications, but rather O(log(n)) algorithms were used (like balanced trees), despite the fact that balanced trees had average running time O(log(n)) while hash tables have average running time near O(1) (I don't remember exact relation now).