Is the asymptotic performance of bitcoin O(n) relative to the block chain length? If I want the latest information (ie. account balance) of account A do I have to traverse the entire block chain to get that info or is the relevant information store in the latest block or some other companion data structure?

If I have to traverse the entire block chain, is there going to be scalable problem as block chain grows?
You have to traverse entire blockchain. At the lowest bitcoin level there is no accounts, there is concept of "unspent output". Bitсoin clients (excluding light versions) should support index of all transactions with unspent output, in order to validate transactions quickly. That means bitcoin clients doesn't actually scan entire blockchain, they just know balance of all accounts.

You are right, it can cause scalability problem, if bitcoin become more valuable, and count of transactions with unspent output will grow very quickly.