O((log n)^2)

Well, Jeroen's and Mike's algorithm is obviously $O((log n)^2)$; just let $n = 2^m - 1$ and see how much work it does. I was hoping to see an $O(log n)$ algorithm which doesn't need $O(log n)$ memory, but I suspect it doesn't exist. An $O(1)$ solution in the spirit of Sikachu!'s:

isOdd = odd

Yes, Haskell has a standard library function to test if a number is odd.

Alexey Romanov said

Well, Jeroen's and Mike's algorithm is obviously $O((log n)^2)$; just let $n = 2^m - 1$ and see how much work it does.

I was thinking that it was more than O(log n) — as I said when I posed the question — but I still find I get easily confused with the Big O stuff :) It doesn't always seem obvious to me which are the terms to ignore, especially when the logs turn up. I guess I need to practice more.

I now also realise that I didn't describe the O(n) solution, which my wife immediately came up with as we discussed on the way back from dinner just now. It's simply a matter of subtracting two until you get to either zero or one. Something like the following (off the top of my head):

isOdd 0 = true
isOdd 1 = true
isOdd n = isOdd (n-2)

I was hoping to see an $O(log n)$ algorithm which doesn't need $O(log n)$ memory, but I suspect it doesn't exist.

I shouldn't think so either. It feels like the sort of thing that should be provably so though, not that I'm about to embark on trying to prove it :)

Kirit Sælensminde said

isOdd 0 = true
isOdd 1 = true
isOdd n = isOdd (n-2)

That's actually pretty stupid isn't it…

isOdd 0 = false
isOdd 1 = true
isOdd n = isOdd (n-2)