Code Kata 3: How Big, How Fast?

This one helps you quickly estimate sizes and speed.
http://codekata.pragprog.com/2007/01/kata_three_how_.html

How Big?

How many bits?

For this one, the way I thought about it is that 10 bits is roughly 1000 (2^10).

11 bits gives you roughly 2000 (2^11).

A pattern emerges as such: 2000 = 1000 * 2 ~ 2^10 * 2^1 = 2^(10+1).

Hence, you can quickly figure out a rough approximation by seeing how many multiples of 1000 there are and then figure out the leftovers.

• 1,000 ~ 2^10
• 1,000,000 ~ 2^20
• 1,000,000,000 ~ 2^30
• 1,000,000,000,000 ~ 2^40
• 8,000,000,000,000 = 1,000,000,000,000 * 8 ~ 2^40 * 2^3 = 2^43

How much space?

For a town of 20,000 residences, to store their names, addresses, and phone numbers, we can assume that we need about 200 characters per resident. This gives us 20,000 * 200 which is 4,000,000 characters. If each character takes up a byte, then we end up with roughly 4MB of data.

Binary trees!

Storing 1,000,000 integers in a binary tree will require 1,000,000 nodes. In the best case (balanced), the number of levels will be log2(1,000,000). Using our approximation technique from above, that would be roughly 20 levels. Any worse then a balanced tree would have more levels up to 1,000,000 levels. The space required to hold a tree like this would be calculated by noticing what data each node needs to hold. Each node needs to hold its own value, a pointer to the left child, and a pointer to the right child. If each piece of data requires 32 bits (4 bytes), then each node requires 12 bytes. This totals 12,000,000 bytes or 12MB of data.

How fast?

How long?

Assuming that each page in the book has roughly 200 characters. Each character takes up a byte. This means we have roughly 240,000 bytes to send. A 56kb/s modem translates to a 7,000B/s modem. This means it would take roughly 350 seconds which is roughly 6 minutes.

Binary search!

It takes 4.5mS to search 10,000 entries and 6mS to search 100,000. There is 10x more to search and it was done in 1.5mS more time. Hence, for 10,000,000, it should take roughly 9mS.

Brute force

There are 96^16 possible passwords.

A rough estimation would be 100^16 = (10^2)^16 = 10^32.

Since we can do 1000 searches per second, this would take 10^32 / 10^3 = 10^29 seconds to perform.

There are 86,400 seconds in a day which is roughly 100,000 seconds. This gives us 10^24 days.

Dividing by 365 is a little hard to do but dividing by 1000 is "close enough". This gives us 10^21 years.

Brute force is definitely not a viable approach.