![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
A tiny bit of math geekery this morning
Dec. 8th, 2007 11:41 amOkay, haven't posted in two whole months, I haven't told you what it's like working at Google since the first day, etc. I will say that my lack of blogging here has absolutely nothing to do with my internal-to-Google blog, since I haven't actually signed up for that either.
And this post isn't going to interest most of you who have me on your friends list, but if I waited for that, it'll be another two months or more before I post anything again. So here's a post on something I was thinking about this morning.
I was reading through some of Steve Yegge's old blog ("who is he?", you ask? He's just this guy that used to work at Amazon, now works for Google, and had an Amazon-internal blog that he made mostly public after leaving Amazon. Some of it's interesting) about interviewing programmers and he gave this as an example of the naive solution to the problem "find the nth Fibbonacci number":
One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2n).
That didn't feel right to me - I mean, clearly it is O(2n) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2n). So what is a tight bound?
It turns out that this algorithm is actually ϴ(fib(n)), which is to say that it's ϴ(φn), where φ is the golden ratio (1 + √5)/2.
Why is this? Well, I think I'll leave that as an exercise for the reader, or maybe I'll add it later to this post underneath a cut tag. Suffice it to say that there's a nice recurrence relation that defines the number of invocations of fib necessary to calculate the nth Fibbonacci number, and that it requires a bit of fiddling after that, but not too much.
Anyway, that's something I was thinking about this morning.
And this post isn't going to interest most of you who have me on your friends list, but if I waited for that, it'll be another two months or more before I post anything again. So here's a post on something I was thinking about this morning.
I was reading through some of Steve Yegge's old blog ("who is he?", you ask? He's just this guy that used to work at Amazon, now works for Google, and had an Amazon-internal blog that he made mostly public after leaving Amazon. Some of it's interesting) about interviewing programmers and he gave this as an example of the naive solution to the problem "find the nth Fibbonacci number":
static long fib(int n) {
return n <= 1 ? n : fib(n-1) + fib(n-2);
}
One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2n).
That didn't feel right to me - I mean, clearly it is O(2n) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2n). So what is a tight bound?
It turns out that this algorithm is actually ϴ(fib(n)), which is to say that it's ϴ(φn), where φ is the golden ratio (1 + √5)/2.
Why is this? Well, I think I'll leave that as an exercise for the reader, or maybe I'll add it later to this post underneath a cut tag. Suffice it to say that there's a nice recurrence relation that defines the number of invocations of fib necessary to calculate the nth Fibbonacci number, and that it requires a bit of fiddling after that, but not too much.
Anyway, that's something I was thinking about this morning.