The implementation of a new computer science (CS) curriculum in high schools which includes all the basic elements of traditional CS programs, motivated a research to determine how students conceive the very fundamental notion of efficiency. Since this was the first time that algorithm efficiency was integrated into a high school curriculum, our study was crucial for further implementation of the program. This paper describes a study that revealed misconceptions in perceiving the efficiency of algorithms by high school students. We discuss the results, provide some indication of the roots of these misconceptions, suggest ways to prevent them, and recommend further research.