4.2.8

Deduce the efficiency of an algorithm in the context of its use.

*Teaching Note:*

Students should understand and explain the difference in efficiency between a single loop, nested loops, a loop that ends when a condition is met or questions of similar complexity.

Students should also be able to suggest changes in an algorithm that would improve efficiency, for example, using a flag to stop a search immediately when an item is found, rather than continuing the search through the entire list.

Sample Question 2 - **FORMER CURRICULUM **(No BigO knowledge required now.):

State the efficiency of searching a binary tree. [1 mark]

JSR Notes:

The first Teaching Note (see above):

` 350 notes Intro to Efficiency of Algorithms and "Big O"`

But do note that "Big O" is not part of the curriculum per se, so you should be clear what you are communicating if you use the words "Big O". So mention that Big O states a general efficiency of an algorithm, and then go on to explain exactly why Big O log 2n, for example, applies in a certain algorithm.

So, here's a specific example:

*"This algorithm (a search through a binary tree) has an efficiency, as stated in "Big O" terms of Big O log 2 n. As the data set gets larger the relative efficiency actually increases exponentially. This is because at each step in the search (in a mostly balanced tree) about half of the remaining nodes do not have to be searched. So, for example, if there were approximately 1 000 000 nodes in the tree, the maximum number of steps taken to find any particular element would be approximately 20."*

The second Teaching Note (see above):

Recall different versions of sorts:

`330 notes Sorting`