Any one who is facing dilemma about the above question should see the following video from 44:20 onward:
Data Structures and Algorithms – Richard Buckland on YouTube
Actually the entire video is very useful for anyone who is interested in understanding the basic of Complexity of Algorithms.
– Dipto Sarkar