typodupeerror

## severoon's Journal: Big-O Versus Medium-O

Journal by severoon

Did that title get your attention? Sorry to disappoint, but this essay isn't about that. :p phfffbbt

Originally, this was to be part of Big-O Notation , but I suspect several people reading this will already be quite familiar with Big-O notation and won't need the primer, so I've split this off.

Order-of-magnitude analysis can be used in two different ways, the way I described in Big-O Notation , a computer science-y, abstract kind of way, and the way I alluded to in Indirect Thinking , a practical kind of way, used to arrive at an actual concrete value. This essay addresses the latter.

For reasons explained in previous essays, it is often useful to gauge the order of a number. In its simplest form, this can be done directly on a number, such as 1040. What is the order of 1040? If you think back to algebra, you'll remember that the order of a polynomial is simply the highest power of the independent variable. For instance, the order of

f(x) = x^3 + 2*x^2 - 4

is 3 because that's the highest exponent of x, found in the x^3 term. You might also remember that regular, everyday, run-of-the-mill numbers such as 1040 have a "polynomial expanded form in their base." Put simply, that means we can write 1040, a base-10 number, as a polynomial (note the "independent variable" in this expansion is the base--10--and the coefficients of those terms, which are bolded, form the digits of the number itself):

1040 = 1*10^3 + 0*10^2 + 4*10^1 + 0*10^0,

or more simply, we can write the expansion as a function of its base b=10 and we drop the zero terms:

f(b) = 1040 = b^3 + 4*b,

So, the order of 1040, therefore, is 3.

This information about 1040, or any other number, is useful mainly for the purpose of comparison. If we find ourselves in a situation where we must compare two numbers of vastly different scales, order-of-magnitude comparison brings such comparisons down into the realm of numbers we can grasp directly. For instance, we might wonder how many Earths could fit inside the surface of the sun, approximately? Is it a thousand? Maybe ten thousand? (That seems like too many, doesn't it?) This is a question that has undoubtedly been answered before, but it would probably take more research than we're willing to do to answer such a frivolous question just for the sake of interest. That is, if we try to find the result of this calculation written up somewhere. On the other hand, it's very easy to find out the radius of the Sun and Earth, and with a little order-of-magnitude calculatin', we can quickly find out the answer for ourselves.

So, I type sun into the Wikipedia and find out that the radius of the Sun is about 110 times that of the Earth [source]. (Note that I need not concern myself with the long, messy number that represents the actual radius...another nice thing that often occurs when doing order-of-magnitude calculations.) I happen to know that the volume of a sphere is 4/3 the cube of its radius (if you didn't know this, this information is also readily available). So if we let rE be the radius of the Earth, we can quickly figure the volume of the Earth, vE, compared to the volume of a sphere with a radius 110 times that size (the volume of the Sun, vS):

vE = 4/3*rE^3
vS = 4/3*(110*rE)^3 = 4/3*110^3*rE^3

Since we're only concerned with order-of-magnitude here, I can simply drop all terms that are of a smaller order than I want to deal with. I can even turn the 110 into 100, the justification being that 100 is very close and happens to fall exactly on an order-of-magnitude boundary for base-10:

vE = rE^3
vS = 100^3*rE^3

If we divide these two quantities, we get our answer:

vS/vE = 100^3*rE^3/rE^3 = 100^3 = (10^2)^3 = 10^6

In other words, the volume of the sun is about 6 orders-of-magnitude larger than the volume of the earth--we should be able to fit about one million Earth-sized planets inside the Sun's volume. (If you do the actual calculations, you'll see that the real answer is roughly 1,331,000--this assumes that each Earth-sized planet is ground up and dumped into a bin the volume of the Sun. It would be less if we were to consider packing hard, Earth-sized spheres into a Sun-shaped and Sun-sized volume because spheres do not pack the space as tightly as Earths that made their way through a cosmic coffee grinder.) Wow--how reasonable it seemed before to say that 10,000 Earths probably couldn't fit into the Sun, hm? As it turns out, that many Earths would only fill up about 1% of the Sun's volume, and it wasn't difficult at all, using order-of-magnitude, to see how far off we'd been.

So, that was an interesting diversion, but now we get to the real point. We accept that using order-of-magnitude brings us a powerful new tool--it allows us to compare numbers of vastly disparate sizes. This works because the numbers involved in order-of-magnitude calcuations are powers of 10, which are so small and managable. The difference between a thousand and a million becomes simply 3. Even if we consider the vast theoretical extremes of our universe, the numbers remain very manageable. The "fundamental unit" of distance (roughly speaking, the smallest distance that can theoretically occur) is about 10^-35 meters. The diameter of the known universe since the Big Bang has expanded to roughly 100 billion light years, or about 10^27 meters. That means our universe contains, when speaking about matters of physical distance, only about 60 (give or take) orders of magnitude total. Only 60.

Think about that for a moment. This means that, no matter what size an object we happen to be discussing, that object's relationship with the smallest theoretical measureable distance can be represented using a number between 0 and 60. Or, alternatively, we can compare the size of any object at all to the size of the known universe using a number between 0 and 60. This brings such mind boggling differences into the realm of what our minds can manage.

So much so, in fact, that it lead me to think that our minds would probably have no trouble at all dealing with numbers that are even slightly larger than from 0 to 60. The 60 orders of magnitude present in our universe is only true if we assume we're working in base-10. But why work in base-10? Clearly, if we used a smaller base than 10, we might gain some fine structure without costing us any manageability. What if we went to the smallest integral base available, base-2, instead? Then what would we find? Would the orders get so large that we would find ourselves outside the realm of the manageable? Well, let's see.

10 is about 2^3.33. This is not exact, but it's convenient to think of it as a nice round fraction, so I'll use 2^(10/3). If I remember my basic numbers correctly, we can convert powers of ten to powers of two simply by multiplying the exponent of ten, then, by 10/3. Let's see if I'm right. We'll figure out, for various powers of ten, what the corresponding powers of two are:

10 = 2^(10/3)
10^2 = (2^(10/3))^2 = 2^(20/3)
10^6 = 2^(6*10/3) = 2^20

These equations aren't exactly true, but they're all pretty close (10^6=1,000,000 and 2^20=1,048,576, not exactly the same, but close enough for our purposes). That means our range expanded from 0 to 60, using base-10, by a factor of 10/3 to 0 to 200. This is definitely still manageable! And, it provides a much finer scale for us to work with. For instance, in base-10, the following numbers are all of the second order of magnitude: 110, 130, 480, 780. All of these numbers fall into different base-2 orders, though...respectively: 6, 7, 8, and 9. Even with this finer level of granularity, we're guaranteed that at the extremes the numbers will still always be restricted to the realm of the manageable.

You might agree that there's benefits to comparing orders in base-2, but argue that it's not practical because people have no reference point for working in this base, whereas base-10 comes naturally to most people...you just count the digits. I would reply, though, that with the tiniest bit of effort, anyone can think in base-2. Because of computers, everyone already knows several benchmarks along the progression of the base-2 system. No one buys 100MB or 200MB of RAM, we buy 128MB (2^7), 256MB (2^8), or 1GB (which is 2^0 gigabytes, 2^10 megabytes, or 2^20 bytes). Furthermore, the two bases tend to align remarkably well every three orders; 1000 is roughly 2^10, 1 million is about 2^20, 1 billion is about 2^30, and so on.

It's not as far-fetched or abstruse as one might think, and it makes order-of-magnitude comparison that much more useful.

This discussion has been archived. No new comments can be posted.