Transaction verification, computationally expensive?

[int]

I have a question about transaction verification.

Let's say TX1 transfers some bitcoins from person A to B, and then say 5 years later I create a transaction TX2 (from A to C) that references the same output as TX1 did, for the same amount. This would be double spending, but to prevent it, wouldn't you need to go through all the blocks (and all the transactions) in history, in order to find TX1 and thus disqualify TX2?

Suppose A had 10 coins to begin with. TX1 transferred 8 coins A->B. TX2 wants to transfer 2 coins to A->C. In this case TX2 would be valid. To validate TX2 you would have to search through all the transactions in all the blocks after TX1 was posted, and check that there wasn't a TX3 that depleted A's balance to below 2 coins.

If TX1 and TX2 are years apart, then the number of transactions to check can be extremely large. It would grow as O(n), where n is the number of transactions historically. Wouldn't this cause a problem?

[Maged]

Whenever an output is spent, it is entirely spent. The remaining amount is returned to you at a new address in that transaction. Once a spent transaction is buried under enough blocks, it can be safely deleted, should your client choose to delete it.

[int]

Whenever an output is spent, it is entirely spent. The remaining amount is returned to you at a new address in that transaction. Once a spent transaction is buried under enough blocks, it can be safely deleted, should your client choose to delete it.

A has 10 coins sitting at a certain output O1. To transfer 8 coins to B from that output, you create a transaction TX1 that references it (and thus entirely spends it) as input, and lists two new outputs : 8 coins to B and 2 coins back to A.

Then A decides to double spend, and creates TX2 where he references O1 again as input. To verify TX2 you still need to know if O1 was spent or not. How would you know that without going through all the historical blocks/transactions to find TX1, the transaction that spends it?