Largest puzzle solvable in one second, assuming it takes f(n) microseconds?

I have this ques开发者_运维知识库tion:

f(n) = log(n) (it's log base 2 btw)

What is the largest size n of a problem that can be solved in one second, assuming the problem takes f(n) microseconds?

Well since f(n) is log(n), the problem takes log(n) microseconds, right? And there are a million microseconds in a second, right? So I set it up like this:

log(n) = 1000000

But that gives 2^1000000 as an answer, and that's an absolutely obnoxiously huge number. Am I doing something wrong?

---

That's fine. O(log(n)) algorithms are extremely fast.

Of course in real life f(n) won't be log(n) forever, if you're working on some data-set, you'll run out of memory and start to hit disk which is going to be slow, and some point later you'll run out of all the disk space on earth...

---

Your math is correct.

An algorithm that runs in log(n) time is one that can cut the size of the problem in half each time. An example would be finding an item in a binary search tree. The worst case would be if the item you are looking for is located in one of the leaves.

So each time you pick a child, you cut off half the tree. At the start you have 2^1 000 000 nodes. When you go down to the next child you have half as many nodes, 2^999 999. After 1 million operations you should be at the leaf that contains the node you were looking for.