### A tiny bit of math geekery this morning

Dec. 8th, 2007 11:41 am**dtm**

Okay, 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

One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2

That didn't feel right to me - I mean, clearly it

It turns out that this algorithm is actually ϴ(

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

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

*n*th 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(2

^{n}).That didn't feel right to me - I mean, clearly it

*is*O(2^{n}) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2^{n}). 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*n*th 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.

## no subject

Date: 2007-12-11 04:50 pm (UTC)cheshirecatco.livejournal.com## no subject

Date: 2007-12-12 06:27 pm (UTC)dtmt(n) = t(n-1) + t(n-2) + 1

to proving that this sequence is (eventually) bounded by constant multiples of fib(n).

## no subject

Date: 2008-07-22 12:43 am (UTC)blasdelf.livejournal.com