That's hardly an improvement and it won't be usable. You could say the same about linear search and binary search: "those become expensive for large data sets". Ditto about bubble sort and quick sort. We need a constructive metric that would give us a ballpark figure answers to: "if I increase the input hundred fold how that'll affect running time and memory consumption?". Look how Knuth defines complexity of bubble sort for example:
This is overly precise, and would take a heck amount of time to analyse for a reader (let alone to calculate properly for a writer!) but if to choose between this and your other extreme: "this can be prohibitively expensive" I have to choose Knuth's version. IMHO a middle ground fix of O-notation (which specifies what units it is expressed in) is the way to go.
As @Nevin by units I don't mean whether those units are seconds vs nanoseconds... but whether they are seconds vs "comparisons" vs "hash calculations" vs "callouts to this and that function" etc. To put it differently, if units are units of time (ages or cpu clocks) - fine, we could omit those by default as that would be assumed, but so long the units are not directly proportional to time but affected by something else (e.g. the key size in the dictionary subscript example) – we need to know those details by reading the documentation. "In the best case scenario directory lookup does one hash calculation and one EQ comparison of the passed key" would do for me if we are afraid to scary readers with Oh-big notation.
Here's an example that illustrates the relevance and importance of units in O() notation.
// Complexity: O(1)
func foo1(items: [String]) -> Int {...}
// Complexity: O(1)
func foo2(items: [String]) -> Int {...}
// Complexity: O(1)
func foo3(items: [String]) -> Int {...}
// Complexity: O(1)
func foo4(items: [String]) -> Int {...}
All foo's are marked with O(1) and when you test those they will all run in roughly 2 seconds each. If you try them with a different number of items (1, 1K, 1M) - that will not affect their execution time, indeed, so O(1) makes sense, right?
If you test further you'd notice these significant differences: foo4 timing would be pretty much unaffected regardless of whatever you come up with, foo3 will run 100x times slower on 10 year's old hardware (or in debug configuration), on the equal hardware foo2 execution time will be linear with the length of the first character of the first string, and foo1 execution time will be linear with the length of the first string itself (e.g. 3 seconds for 100 byte string, 30 seconds for 1K string, 300 seconds for 10K string, and so on).
What's inside foo's
// Complexity: O(1)
func foo1(items: [String]) -> Int {
let firstString = items.first!
var s = 0
for _ in 0 ..< 70_000_000 {
s &+= firstString.hashValue
}
return s
}
// Complexity: O(1)
func foo2(items: [String]) -> Int {
let firstString = items.first!
let firstCharacter = firstString.first!
var s = 0
for _ in 0 ..< 180_000_000 {
s &+= firstCharacter.hashValue
}
return s
}
// Complexity: O(1)
@_optimize(none)
func foo3(items: [String]) -> Int {
var s = 0
for i in 0 ..< 10_000_000 {
s &+= I
}
return s + Int(items.first!.unicodeScalars.first!.value)
}
// Complexity: O(1)
func foo4(items: [String]) -> Int {
sleep(2)
return Int(items.first!.unicodeScalars.first!.value)
}
Suggested notation fix for this example:
// Time complexity: O(1) first string hash value calculations
func foo1(items: [String]) -> Int {...}
// Time complexity: O(1) first character of the first string hash value calculations
func foo2(items: [String]) -> Int {...}
// Time complexity: O(1) CPU instructions
func foo3(items: [String]) -> Int {...}
// Time complexity: O(1) seconds
func foo4(items: [String]) -> Int {...}
All that was needed was specifying the units. It's still not "War & Piece" nor the Knuth version above in length and details but provides a valuable insight on complexity. It's still a bird eye overview on what's going on (e.g. we don't specify the nature of CPU instructions in foo3, we don't nitpick that beyond O(1) seconds we are doing something extra in foo4, etc).
