Estimation

Questions from Skiena, Algorithm Handbook, Chapter 1

Pages of books

Question 1-19 a) Do all of the combined the books you own have at least 1M pages?

Each book has O(100) pages - let's say, O(250) pages. Using either 1E2 or 2.5E2 as number of pages per book.

100 pages per book: 1 million pages is 1E6 pages x (1 book/1E2 pages) = 1E4 books = 10,000 books. Nope.

250 pages per book: 1 million pages is 1E6 pages x (1 book/2.5E2 pages) = 4E3 books = 4,000 books. Still nope.

Question 1-19 b) How many total page are in the school library?

Cascading estimations here.

1 book ~ 100 pages.

1 shelf ~ 10 books.

1 long bookcase ~ 100 shelves.

1 section ~ 10 long bookcases.

1 small library ~ 10 sections

1 big library ~ 100 sections

1 very large library ~ 1000 sections

(Note: can squeeze in additional factors of 10 in by turning one 1 into one 2.5 and one 1 into one 4.)

Number of pages in the library:

1 small library x (10 sections/1 lib) x (10 bookcases/1 section) x (100 shelves/1 bookcase) x (10 books/1 shelf) x (10 pages/1 book)

= 10 x 10 x 100 x 10 x 10

= 100 x 100 x 100

= 1 million pages for a small library (10k books)

= 10 million pages for a big library (100k books)

= 100 million pages for a very large library (1M books)

(This estimate does seem on the low side, probably additional factors of 10 missing. Plus or minus 2 orders of magnitude.)

Note: the NY Public Library is estimated to have somewhere around 3 million books. So, this seems to be in the right general ballpark.

Number of words in Skiena textbook

Question: Number of words in the Skiena textbook?

A single full page is about 15 words per line, about 40 lines per page, for a total of about 600 words per page.

The total number of pages is 700.

So the absolute upper bound, assuming every page is densely packed, is 420,000 words.

We can get a better estimate by assuming that 2/3 of the pages are full (600 words), and 1/3 of the pages are occupied by tables, figures, and white space (half full, or 300 words).

Do the half-full pages plus the full pages:

Nwords = 700 pages x (33 half-full pages/100 pages total) x ( .50(600) words / 1 half-full page) 
        + 700 pages x (66 full pages/100 pages total) x (1.0(600) words / 1 full page)

Nwords = (700)(600)(.33*.5 + .67)

Nwords = 420000(.7)

Nwords = 290,000

So the grand total is in the ballpark of 300,000 words. (Intuitively, this seems a bit on the long side.)

Number of hours in 1M seconds

How many hours are in 1M seconds? How many days? Do the math in your head.

Here we use that trick of using quarters when doing scale analysis.

3600 seconds per hour ~ 2500

24 hours per day ~ 25

1 M seconds = 1E6/2.5E3 = 4E(5-3) = 4E2 = 400 hours

1 M seconds = 400 hours/(25 hr/day) == 16 days

The actual value?

1E6 x (1/3600) x (1/24) = 11 days

Trick here is not to do just an order of magnitude estimate, but to make use of quarters as well. 1000/25, not just 1000/10. (If you don't do this, twice, you'll be off by an order of magnitude.)

Number of towns and cities in US

Question: Estimate the number of towns and cities in the United States.

Here we use the 80/20 heuristic. We assume that 80% of the population lives in large cities, the remaining 20% live in smaller cities.

Then, of that remaining 20%, we assume that 80% of them live in large cities, and 20% of them live in smaller cities.

Of that remaining 20%, etc.

Do this multiple times, splitting into groups that live in cities of 1M, 100k, 10k, 1k, 100, and 10 (Note: if you start with 10 M, it really throws off the estimate.) Then we get:

When we combine this with the total population of 3 M people, we get the total number of cities/towns that people live in (that is, if 80% of 300 M people live in cities of 10 M people or more, we can determine how many 10 M person cities there are; etc.)

Here's the nested expression (p = people):

$300M=3e8p\times \left({\dfrac {.80p}{1e6p/city}}+.20\times \left({\dfrac {.80p}{1e5p/city}}+.20\times \left({\dfrac {.80p}{1e4p/city}}+.20\times \left({\dfrac {.80p}{1e3p/city}}+.20\times \left({\dfrac {.80p}{1e2p/city}}+{\dfrac {.20}{1e1p/city}}\right)\right)\right)\right)\right)$

Plugging this into Wolfram Alpha gives 17,040.

This is pretty damn close to the number of "incorporated places" listed by the census: 19,354 [1].

Sorting algorithm time

A sorting algorithm takes 1 second to sort 1000 items.

How long will it take to sort 10,000 items if:

a) O(n^2) algorithm?

b) O(n log n) algorithm?

a) If O(n^2) algorithm:

$N_{ops}\sim 1000^{2}\sim (1e3)^{2}\sim 10^{6}ops$

which gives us a time per operation of 1 microsecond:

$t\sim {\dfrac {T}{N_{ops}}}\sim {1}{10^{6}}\sim 10^{-6}s/op$

Now, for 10,000 items,

$N_{ops}\sim (10,000)^{2}\sim (10^{4})^{2}\sim 10^{8}$

and this gives a total time of

$T\sim N_{ops}t\sim (10^{8})(10^{-6})\sim 10^{2}\sim 100seconds$

The quadratic algorithm will sort 10,000 items in 100 seconds.

For the superlinear algorithm,

$N_{ops}\sim 1000log1000\sim 3000ops$

This gives time per operation of

$t\sim {\dfrac {T}{N_{ops}}}\sim {\dfrac {1s}{3000ops}}\sim 3\times 10^{-}3s/op$

So for 10,000 items,

$N_{ops}\sim (10,000)log(10,000)\sim 4(10,000)\sim 4\times 10^{4}ops$

This gives a total time of

$T\sim N_{ops}t\sim (4\times 10^{4}){\dfrac {3\times 10^{-3}s}{op}}\sim 12\times 10\sim 120s$

The superlinear algorithm will sort 10,000 items in 120 seconds.

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag