Today I am working on (non-coding) Code Kata 3 Kata03: How Big? How Fast? - CodeKata. And I finished the first part: “How Big”

roughly how many binary digits (bit) are required for the unsigned representation of:

1,000 - this is easy to do in head (or perhaps more accurately fingers) 11 bits as 2^11 is 1024 1,000,000 - again easy, shift again 11 bits, so roughly 22 bits 1,000,000,000 - hmm, is not quite aliging to power of 2 mess up my calculations? 33 1,000,000,000,000 - with the same caveat, 44 8,000,000,000,000 - multiple by 8 is shifting by 3, so 47

Quick checkup with a Swift playground:

var num = 8000000000000

var presentation = String(num, radix: 2)

presentation.count

And the result is 43. Hmm, my intuition was a bit off. Turns out I was off by one! 2^10 = 1024, not 2 ^ 11, bummer.

My town has approximately 20,000 residences. How much space is required to store the names, addresses, and a phone number for all of these (if we store them as characters)?

Let’s assign 50 characters for a name, 15 for phone number, let’s present address as two address lines, a zip code, city, state and country = 50 + 50 + 10 (zip code) + 20 (city) + state (50) + country (20) = at max 200 characters but let’s assume conservative 100 chars, so 165 chars * 20000 = with some calculator help is 3 Megabytes

I’m storing 1,000,000 integers in a binary tree. Roughly how many nodes and levels can I expect the tree to have? Roughly how much space will it occupy on a 32-bit architecture?

Worst case is a tree where tree only ever goes left or right, then the depth is 1,000,000. Best case is fully packed tree, where all levels are full and balanced. That is 19 full levels and a lot of nodes on level 20. So best case depth is 20.

Tree node is three items, one number and two pointers. With million nodes that is roughly 3 * 4 bytes * 1M, so roughly 12 MB.