4 ms·
Average Time to Check If an Array Is Sorted
- CharlesMerriam2 10y agoIt is enjoyable to find the mathematics of randomness. You might find two interesting points more related to computer science: 1. A linear search of memory is O(n^1.5), not O(n). Practical issues of caching lead to this empirical formula. This is consistent through L1, L2, RAM, disk caching, and cloud access, at least in practice. 2. Analyzing an algorith for a single processor is a quaint exercise. For example, scanning linear memory is O(n^1.5/p) where p is the number of processors. Yes, this makes me feel old.