3 ms·
The library example is a bad one, since it leads to O(N) and not O(√N), a conclusion that contradicts the thesis. "In general, the amount of books N that fits
by rdiddly 10y ago
The library example is a bad one, since it leads to O(N) and not O(√N), a conclusion that contradicts the thesis.
"In general, the amount of books N that fits in a library is proportional to the square of the radius r of the library, and we write N∝ r²."
No, the number of books N is proportional to the area of the front face of the shelving, not the area enclosed within the circle. Assuming all libraries are the same height, that means N is proportional to the circumference of the circle, which is proportional to r, not r². Meanwhile, assuming that all books are reachable in the same amount of time by the librarian no matter their height on the shelf, that means T ∝ r (as before). Since T ∝ r and N ∝ r, that means T ∝ N or T=O(N).
- yxhuvud 10y agoEh, your library seems to have a very poor use of floor space. Place the shelves well and you will definitely have something that can store books proportional to the area of the library. Hint for more efficient placement: You can put shelves away from the outer wall in arbitrary positions within the circle. At that point, the assumption that the librarian can reach any point in the circle at constant time is blatantly false (as the books closer to the centre will generally be faster to reach).
- rdiddly 10y agoIt's not "my" library, that's how it was defined in the article (Part II).