Content deleted Content added
No edit summary |
Groupthink (talk | contribs) →Fixing this up again: new sec |
||
Line 106:
I changed the introduction to be less technical and contain more applications to the "real world". I think this is more to the proposed standard. Some of the replaced material better belongs in the sections to which it pertains. I'll contribute more as I find time. [[User:Scottcraig|Scottcraig]] 18:03, 17 October 2006 (UTC)
== Fixing this up again ==
I noticed this article in the "pages needing attention" section of the Computer Science project page. I understand that it's already undergone one major rewrite (which I will look over in detail when I have some time) but I have some thoughts off the top of my head that I'd like to share:
# Shouldn't this article be called "Run-time complexity theory"?
# In the opening graf, "scalability" is used to describe algorithm complexity. While this is perhaps an apt analogy, isn't it technically inaccurate to equate the two concepts? "The capacity to handle increasing workloads/throughput" isn't quite the same thing as "the increase in running time as input size increases".
# The Big-O function is mentioned in passing. Small-O, Omega and Theta are not mentioned at all. Neither is the concept of a monotonically increasing function. Shouldn't these concepts be ''central'' to the article?
# I didn't notice any discussion of why theoretical run-time complexity classes are superior to empirical measurements or benchmarks. When I learned run-time complexity, a "classic" example we were given right off the bat was a side-by-side comparison of running times for two machines running two different sorting algorithms. Machine A was the equivalent of a 1980's TRS-80, running an O(n lg n) sort. Machine B was a state-of-the-art (at the time) Pentium 4 running an O(n<sup>3</sup>) sort. For small sizes of n, Machine B was light-years faster, but as the size of n increased, Machine A eventually came to pwn Machine B. I'd like to see a chart like that in the article.
I'll give the page a thorough read and make more detailed suggestions later. [[User:Groupthink|Groupthink]] 13:16, 26 June 2007 (UTC)
| |||