O((log n)^2) Alexey Romanov 30th November, 2008 11:26 (UTC)

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.

O((log n)^2) Kirit Sælensminde 30th November, 2008 15:46 (UTC)
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 :)

```isOdd 0 = true
```isOdd 0 = false