Oddness and evenness

This puzzle is from Jeroen Vermeulen* [*If any body else has any interesting puzzles don't hesitate to let me know.]. He actually suggested it a couple of weeks ago and I've been thinking about it off and on since then (without coming up with any good solutions). The problem is to tell whether a number is odd or even, but there are some restrictions on how you go about it.

Write a function that given a positive integer will return true for even or false for odd. You may use integer addition and subtraction and you may use integer comparison (equality, greater than, etc.). You may not use bitwise operations (shifts, and, or, xor, etc.) and you may not use division (you may use multiplication in as much as it is repeated addition). Modulo is not allowed :)

When Jeroen told me about it he said that there is an O(log n) solution. Having discussed it with Mike he immediately came up with an algorithm, but I don't think his algorithm is O(log n), it's more like O((log n)²) or O((log n)^{log n}) — I'm not sure if that makes any difference from a big-O perspective though.

1. An O(n) algorithm should be fairly simple to come up with I think.
2. Something around O(log n) isn't too hard either.
3. Can anybody come up with something that is faster than O(log n), or provide an outline of a proof — or at least an argument — as to why it isn't possible.

Answers in comments, but for new accounts you'll need to contact me (kirit at kirit dot com) to get posting rights due to spammers.