What's your n? The amount of memory allocated? In that case, I'd be interested to see such an algorithm that takes time O(1) but touches O(n) memory cells in th

What's your n? The amount of memory allocated? In that case, I'd be interested to see such an algorithm that takes time O(1) but touches O(n) memory cells in the process... Obviously you need to include the time your calls take in the analysis, but your example seems ood.