Round 7: Efficiency

(Disorder and order.)

Learning objectives

In this round you will learn …

• … that computing consumes resources, such as energy, time, and memory

• … that a programmer should strive to make efficient use of resources

• … that there are multiple factors that affect efficiency, ranging from algorithms to hardware

• … to measure resource consumption (running time in particular) and analyze the results

• … to quantify resource consumption mathematically as a function of the size of the input

• … the big O notation to express the rate of growth of a function

• … the importance of efficient algorithms and structured data

• … a case study in algorithms that search data

  • … that unstructured data is slow and inefficient to search

  • … that unstructured data may be indexed (for example, sorted)

  • … how to search a massive amount of sorted data really, really fast with binary search

(Material that is marked with one or more asterisks (*) is good-to-know, but not critical to solving the exercises or passing the course.)

Download

To follow and play around with the timer and matrix examples in this section you can download and import this source code package.