Is the time taken for the verification of a transcation not much relevant? By verification I do not mean the puzzle solving/hash calculating part but the part involving searching all of the blocks to check if the transaction is valid or not? 

For example if A transferred some coins to B ten years ago and after that A didn't make any transaction. Now A wants to make some transaction. To verify this transaction, the miners need to know A's balance which was last updated ten years ago. To do this the miners have to traverse through huge number of blocks to the block of then, won't it take much time?
To do this the miners have to traverse through huge number of blocks to the block of then, won't it take much time?


When A wants to make a payment, he would reference the transaction txid and n in the input from where he earnt the bitcoins that he now wishes to spend. Full nodes generate an indexed database of all unspent transaction outputs (UTXOs), and refers to it when checking transactions for validity. This data is stored in $DATADIR/chainstate and aggressively cached in memory. Thus the nodes do not have to go through all the blocks prior to that, because they have all the unspent outputs handy. This functionality also allows full nodes to prune the blockchain to a desired size without losing the capability of verifying the transactions independently.