Is there an error? I think there is a problem in the first implementation in JavaScript of the procedure "searchList()" (in fact the error repeats after this section): in the for loop when is find the "targetNumber", there is a "return" of "index", a variable that isn't changed by its intial value of zero, in fact I tried put "println" around the procedure and it displays always 0 rather than the index of 2. I don't know if I'm wrong, but maybe the variable must be changed in the loop with the value of "i" and in general it's useless to use it, in fact it's sufficent to return "i" instead.

After careful examination, I believe you are correct. That algorithm will only ever return 0 or -1. There should be no "index" variable, and "i" should be returned instead. Good catch! (:

In the Binary search algorithm example, what happens if the sorted list has multiple entries of the target value, for example: numbers [1,2,45,45,45,50,60] and target = 45? In other words, is it possible to use the binary search algorithm for lists with repeated entries?

Yes, the binary search algorithm will work on lists with repeated entries, provided that the list is sorted.

If there's an array that has mixed numbers (like 75, 90, 85, 20, 100, 82) and I wanted to use binary search, I would have to arrange the numbers first right? Otherwise, the search wouldn't work.

Yes, the binary search algorithm only works when applied to sorted arrays.

Hello, are there basic principles or rule used when building up algorithms?

Well, most of the time you want it to be as efficient as possible, which means no unnecessary steps to avoid loss in speed. And you tend to build on what you already know, so many times algorithms are just modifications of previous algorithms. You basically adapt what you already know in order to fix a new problem. But it's not like there is an algorithm to build an algorithm, in many cases you need to be creative.

I ran the 'number of nanoseconds' java script code on the same computer in Microsoft edge and Google chrome, and I got about 150 in Google chrome and about 120 in Microsoft edge; why is Microsoft edge running the java script faster than Google chrome?

There are a variety of possible reasons, not all of them to do with the browser being used. Chrome might use more computer resources for the various other things it is doing in the background. You might have had more tabs open in Chrome, or more applications running at the same time. Background processes on the computer might have been using more computer resources at that time. To get a more accurate answer, you would need to run the program multiple times on each browser at various times to see whether or not the browser is actually the reason the script runs slower/faster.

I am confused by the third javascript code, can you give some explanations about those javascript? Thanks for your work!

The first function is the searchList() function that's being analyzed. The second function is the tester. In the first step a sorted list is created and in the next step a random number is selected for search and then the search is performed a couple of thousand times in order to get the average run time in nanoseconds. The code is already pretty well documented, could you be a little more precise about which part confuses you?

Is there a way of calculating the number of binary search operations that will be required given a list size?

Suppose we have a sorted array of size N. Maximum Number of Comparisons Using Binary Search Algorithm = 1 + ceiling(log_2(N))

Main content

Course: AP®︎/College Computer Science Principles > Unit 4

Lesson 2: Evaluating algorithms

Measuring an algorithm's efficiency

Google Classroom

A good algorithm is correct, but a great algorithm is both correct and efficient. The most efficient algorithm is one that takes the least amount of execution time and memory usage possible while still yielding a correct answer.

Counting the operations

One way to measure the efficiency of an algorithm is to count how many operations it needs in order to find the answer across different input sizes.

Let's start by measuring the linear search algorithm, which finds a value in a list. The algorithm looks through each item in the list, checking each one to see if it equals the target value. If it finds the value, it immediately returns the index. If it never finds the value after checking every list item, it returns -1.

Here's what that algorithm looks like in pseudocode:

PROCEDURE searchList(numbers, targetNumber) {
  index ← 1
  REPEAT UNTIL (index > LENGTH(numbers)) {
    IF (numbers[index] = targetNumber) {
      RETURN index
    }
    index ← index + 1
  }
  RETURN -1
}

Note that this pseudocode assumes a 1-based index for lists.

Let's step through the algorithm for this sample input:

searchList([3, 37, 45, 57, 93, 120], 45)

The algorithm starts off by initializing the variable index to 1. It then begins to loop.

Iteration #1:

It checks if index is greater than LENGTH(numbers). Since 1 is not greater than 6, it executes the code inside the loop.
It compares numbers[index] to targetNumber. Since 3 is not equal to 45, it does not execute the code inside the conditional.
It increments index by 1, so it now stores 2.

Iteration #2:

It checks if index is greater than LENGTH(numbers). Since 2 is not greater than 6, it executes the code inside the loop.
It compares numbers[index] to targetNumber. Since 37 is not equal to 45, it does not execute the code inside the conditional.
It increments index by 1, so it now stores 3.

Iteration #3:

It checks if index is greater than LENGTH(numbers). Since 3 is not greater than 6, it executes the code inside the loop.
It compares numbers[index] to targetNumber. Since 45 is equal to 45, it executes the code inside the conditional.
It returns the current index, 3.

Now let's count the number of operations that the linear search algorithm needed to find that value, by counting how often each type of operation was called.

operation	# of times
Initialize index to 1	1
Check if `index` is greater than `LENGTH(numbers)`	3
Check if `numbers[index]` equals `targetNumber`	3
Return `index`	1
Increment `index` by 1	2

That's a total of 10 operations to find the targetNumber at the index of 3. Notice the connection to the number 3? The loop repeated 3 times, and each time, it executed 3 operations.

Check your understanding

How many operations are required to find the number 3, located at the 1st position in the list?

How many operations are required to find the number 37, located at the 2nd position in the list?

Let's make a table of the number of operations required based on the position of targetNumber in the list.

See if you can fill in the blanks:

location in list	# of operations
1st item in list	Your answer should be an integer, like $6$ ‍ a simplified proper fraction, like $3 / 5$ ‍ a simplified improper fraction, like $7 / 4$ ‍ a mixed number, like $1 3 / 4$ ‍ an exact decimal, like $0.75$ ‍ a multiple of pi, like $12 pi$ ‍ or $2 / 3 pi$ ‍
2nd item in list	Your answer should be an integer, like $6$ ‍ a simplified proper fraction, like $3 / 5$ ‍ a simplified improper fraction, like $7 / 4$ ‍ a mixed number, like $1 3 / 4$ ‍ an exact decimal, like $0.75$ ‍ a multiple of pi, like $12 pi$ ‍ or $2 / 3 pi$ ‍
3rd item in list	10
4th item in list	Your answer should be an integer, like $6$ ‍ a simplified proper fraction, like $3 / 5$ ‍ a simplified improper fraction, like $7 / 4$ ‍ a mixed number, like $1 3 / 4$ ‍ an exact decimal, like $0.75$ ‍ a multiple of pi, like $12 pi$ ‍ or $2 / 3 pi$ ‍
5th item in list	Your answer should be an integer, like $6$ ‍ a simplified proper fraction, like $3 / 5$ ‍ a simplified improper fraction, like $7 / 4$ ‍ a mixed number, like $1 3 / 4$ ‍ an exact decimal, like $0.75$ ‍ a multiple of pi, like $12 pi$ ‍ or $2 / 3 pi$ ‍
6th item in list	Your answer should be an integer, like $6$ ‍ a simplified proper fraction, like $3 / 5$ ‍ a simplified improper fraction, like $7 / 4$ ‍ a mixed number, like $1 3 / 4$ ‍ an exact decimal, like $0.75$ ‍ a multiple of pi, like $12 pi$ ‍ or $2 / 3 pi$ ‍

The best case for an algorithm is the situation which requires the least number of operations. According to that table, the best case for linear search is when targetNumber is the very first item in the list.

What about the worst case? According to that table, the worst case is when targetNumber is the very last item in the list, since that requires repeating the 3 loop operations for every item in the list.

There is actually a slightly worse worst case: the situation where targetNumber is not in the list at all. That'll require a couple extra operations, to check the loop condition and return -1. It doesn't require an entire extra loop repetition, however, so it's not that much worse. Depending on our use case for linear search, the worst case may come up very often or almost never at all.

The average case is when targetNumber is in the middle of the list. That's the example we started with, and that required 3 repetitions of the loop for the list of 6 items.

Let's describe the efficiency in more general terms, for a list of

n

items. The average case requires

1

operation for variable initialization, then

n / 2

loop repetitions, with

3

operations per loop. That's

1 + 3 (n / 2)

This table shows the number of operations for increasing list sizes:

list size	# of operations
6	10
60	91
600	901

Let's see that as a graph:

Generally, we can say that there's a "linear" relationship between the number of items in the list and the number of operations required by the algorithm. As the number of items increase, the number of operations increases in proportion.

Empirical measurements

The number of operations does not tell us the amount of time a computer will take to actually run an algorithm. The running time depends on implementation details like the speed of the computer, the programming language, and the translation of the language into machine code. That's why we typically describe efficiency in terms of number of operations.

However, there are still times when a programmer finds it helpful to measure the run time of an implemented algorithm. Perhaps a particular operation takes a surprisingly long amount of time, or maybe there's some aspect of the programming language that's slowing an algorithm down.

To measure the run time, we must make the algorithm runnable; we must implement it in an actual programming language.

Here's a translation from the pseudocode to JavaScript:

function searchList(numbers, targetNumber) {
    for (var index = 0; index < numbers.length; index++) {
        if (numbers[index] === targetNumber) {
            return index;
        }
    }
    return -1;
}

The program below calls searchList() on the list of six numbers and reports the time taken in milliseconds.

If your computer is as fast as mine, then you'll see 0 milliseconds reported. That's because this algorithm takes way less time than a millisecond. Our JavaScript environment can't measure time in units less than milliseconds, however.

Here's what we'll try instead: we'll call searchList() 100,000 times, record how many milliseconds that takes, and divide to approximate the number of nanoseconds per call. That's what this program does:

On my computer, that reports around 150 nanoseconds. There are 1,000,000,000 nanoseconds in a second, so that's really quite fast. In a faster language, environment, or computer, it could be even faster.

That only tells us the average run-time for searchList() on a list of 6 numbers. We care more about how run time increases as the input size increases, however. Does it keep increasing linearly, like our above analysis predicted?

The program below reports the run-time for lists of 6 numbers, 60 numbers, and 600 numbers.

Here are the results from one run on my computer:

list size	nanoseconds
6	50
60	420
600	3430

This graph plots those points:

As predicted, the relationship between the points is roughly linear. As the number of operations increases by a factor of 10, the nanoseconds increases at nearly that same factor of 10. The exact numbers aren't as clean as our operation counts, but that's expected, since all sorts of real world factors can affect actual running time on a computer.

Improving efficiency

Multiple algorithms can correctly solve the same problem, but with different efficiencies. That's when measuring algorithmic efficiency really matters, to help us choose the more efficient algorithm.

The linear search algorithm can find a result in linear time, which is pretty good—but what if there was a more efficient algorithm? In fact, there is, at least for the case of a sorted list.

The binary search algorithm can efficiently find a value in a sorted list. The algorithm starts by checking to see if the target value is higher or lower than the middle value of the list. If it's higher, it knows that it can't be in the first half of the list. If it's lower, it knows it can't be in the second half of the list. The algorithm then repeatedly compares the target value to the middle value of the remaining list, halving the list each time until it locates the value.

Here's what that looks like in pseudocode:

PROCEDURE searchList(numbers, targetNumber) {
  minIndex ← 1
  maxIndex ← LENGTH(numbers)
  REPEAT UNTIL (minIndex > maxIndex) {
    middleIndex ← FLOOR((minIndex+maxIndex)/2)
    IF (targetNumber = numbers[middleIndex]) {
      RETURN middleIndex
    } ELSE {
       IF (targetNumber > numbers[middleIndex]) {
         minIndex ← middleIndex + 1
       } ELSE {
         maxIndex ← middleIndex - 1
       }
     }
  }
  RETURN -1
}

Let's step through this algorithm. Since the linear search example used a sorted list, we can try this algorithm on the same list:

searchList([3, 37, 45, 57, 93, 120], 45)

The algorithm starts off by initializing minIndex to 1 and maxIndex to 6.

Iteration #1:

It checks if minIndex (1) is greater than maxIndex (6). Since it is not, it executes the code inside the loop.
It sets middleIndex to the average of minIndex and maxIndex, rounded down. That's FLOOR((1+6)/2), so middleIndex stores 3.
It checks if targetNumber is equal to numbers[middleIndex]. Since numbers[3] and targetNumber are both 45, that conditional is true, and it returns the index 3.

Wow, this binary search algorithm found the targetNumber on the very first loop. That took just 5 operations, 2 for the initialization step and 3 operations for the loop. As it turns out, this is the best case for this algorithm: the situation where the target value is in the middle of the list.

What about the very worst case, when the value isn't in the list at all? Let's try finding the number 13 in that same list.

The algorithm starts off by initializing minIndex to 1 and maxIndex to 6.

Iteration #1:

It checks if minIndex (1) is greater than maxIndex (6). Since it is not, it executes the code inside the loop.
It sets middleIndex to FLOOR((1+6)/2), so middleIndex stores 3.
It checks if targetNumber (13) is equal to numbers[middleIndex] (45). They are not equal, so it continues to the next condition.
It checks if targetNumber is greater than numbers[middleIndex]. It is not, so it continues to the ELSE.
It sets maxIndex to middleIndex - 1, so maxIndex is now 2.

Iteration #2:

It checks if minIndex (1) is greater than maxIndex (2). Since it is not, it executes the code inside the loop.
It sets middleIndex to FLOOR((1+2)/2), so middleIndex stores 1.
It checks if targetNumber (13) is equal to numbers[middleIndex] (3). They are not equal, so it continues to the next condition.
It checks if targetNumber is greater than numbers[middleIndex]. Since it is greater, it sets minIndex to middleIndex + 1, so minIndex is now 2.

Iteration #3:

It checks if minIndex (2) is greater than maxIndex (2). Since it is not, it executes the code inside the loop.
It sets middleIndex to FLOOR((2+2)/2), so middleIndex stores 2.
It checks if targetNumber (13) is equal to numbers[middleIndex] (37). They are not equal, so it continues to the next condition.
It checks if targetNumber is greater than numbers[middleIndex]. It is not, so it continues to the ELSE.
It sets maxIndex to middleIndex - 1, so maxIndex is now 1.

Iteration #4:

It checks if minIndex (2) is greater than maxIndex (1). Since it is greater, it does not proceed inside the loop.

The algorithm finally returns -1, signifying the value could not be found.

That was the worst case for the binary search algorithm, and yet, it only required 3 full repetitions of the loop, with around 4 operations per loop. Remember the worst case for linear search on a list of 6 numbers? It had to loop through every number, so it required a full 6 repetitions.

That's the beauty of binary search: each loop divides the search space in half, so the algorithm has increasingly less numbers to look through.

This table shows the number of loop repetitions required for various list sizes, in the worst case:

list size	# of loop repetitions
6	3
60	6
600	10

With binary search, a list of 600 items only requires 10 loop repetitions! With linear search, that same list would require 600 loop repetitions.

Here's that table in graph form:

As you can see, binary search is much more efficient than linear search, especially as the list size grows. Mathematically, we can describe the relationship between list size and operations for binary search as "logarithmic", which is a much slower rate of growth than the linear relationship of linear search.

Check your understanding

Your program has a list of 10,000 numbers, sorted from lowest to highest, and you need to see whether a number is in that list.

Which algorithm do you use?

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Do you have any questions about this topic? We'd love to answer—just ask in the questions area below!

Want to join the conversation?

Sort by:

gennarodellaquila1
Posted 3 years ago. Direct link to gennarodellaquila1's post “Is there an error? I thin...”
Is there an error? I think there is a problem in the first implementation in JavaScript of the procedure "searchList()" (in fact the error repeats after this section): in the for loop when is find the "targetNumber", there is a "return" of "index", a variable that isn't changed by its intial value of zero, in fact I tried put "println" around the procedure and it displays always 0 rather than the index of 2. I don't know if I'm wrong, but maybe the variable must be changed in the loop with the value of "i" and in general it's useless to use it, in fact it's sufficent to return "i" instead.
Button navigates to signup pageButton navigates to signup page
(8 votes)
Answer
- Evan
  Posted 3 years ago. Direct link to Evan's post “After careful examination...”
  After careful examination, I believe you are correct. That algorithm will only ever return 0 or -1. There should be no "index" variable, and "i" should be returned instead. Good catch! (:
  Button navigates to signup page
  (7 votes)
Vivor
Posted 2 years ago. Direct link to Vivor's post “In the Binary search algo...”
In the Binary search algorithm example, what happens if the sorted list has multiple entries of the target value, for example: numbers [1,2,45,45,45,50,60] and target = 45?

In other words, is it possible to use the binary search algorithm for lists with repeated entries?
Button navigates to signup pageButton navigates to signup page
(5 votes)
Answer
- KLaudano
  Posted 2 years ago. Direct link to KLaudano's post “Yes, the binary search al...”
  Yes, the binary search algorithm will work on lists with repeated entries, provided that the list is sorted.
  Comment on KLaudano's post “Yes, the binary search al...”
  (4 votes)
24griffithc
Posted 3 years ago. Direct link to 24griffithc's post “What exactly counts as an...”
What exactly counts as an operation? Does returning a value count as an operation?
Button navigates to signup pageButton navigates to signup page
(5 votes)
Answer
evan.clifford
Posted 3 years ago. Direct link to evan.clifford's post “If there's an array that ...”
If there's an array that has mixed numbers (like 75, 90, 85, 20, 100, 82) and I wanted to use binary search, I would have to arrange the numbers first right? Otherwise, the search wouldn't work.
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- KLaudano
  Posted 3 years ago. Direct link to KLaudano's post “Yes, the binary search al...”
  Yes, the binary search algorithm only works when applied to sorted arrays.
  Button navigates to signup page
  (2 votes)
Fredrick Nganga
Posted 4 years ago. Direct link to Fredrick Nganga's post “Hello, are there basic pr...”
Hello, are there basic principles or rule used when building up algorithms?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Martin
  Posted 4 years ago. Direct link to Martin's post “Well, most of the time yo...”
  Well, most of the time you want it to be as efficient as possible, which means no unnecessary steps to avoid loss in speed.
  And you tend to build on what you already know, so many times algorithms are just modifications of previous algorithms. You basically adapt what you already know in order to fix a new problem.
  
  But it's not like there is an algorithm to build an algorithm, in many cases you need to be creative.
  Button navigates to signup page
  (3 votes)
Seven
Posted 4 years ago. Direct link to Seven's post “Would it ever be more eff...”
Would it ever be more efficient to use a binary sorting algorithm first and assigning each number with it's original index, before looking through the list for the target number with a binary search?
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- KLaudano
  Posted 4 years ago. Direct link to KLaudano's post “If you are searching for ...”
  If you are searching for only a single number, it will be more efficient to use a linear search instead of sorting the array and then using the binary search algorithm.
  
  If we simply use a linear search, we will find the number in linear time. Now, suppose we instead decide to sort the array and then search for the number. In the best-case scenario, we might be able to sort the array in linear time, (but it is more likely to take linearithmic time). Then, using a binary search will take logarithmic time. So, even in the best-case scenario, sorting before searching is still less efficient.
  
  Keep in mind, this may not be true if you are searching for multiple numbers in the array. The more numbers you are searching for in the array, the more efficient it will be to sort at the very beginning before performing searches.
  Button navigates to signup page
  (1 vote)
Iggy Belton
Posted a year ago. Direct link to Iggy Belton's post “I ran the 'number of nano...”
I ran the 'number of nanoseconds' java script code on the same computer in Microsoft edge and Google chrome, and I got about 150 in Google chrome and about 120 in Microsoft edge; why is Microsoft edge running the java script faster than Google chrome?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- KLaudano
  Posted a year ago. Direct link to KLaudano's post “There are a variety of po...”
  There are a variety of possible reasons, not all of them to do with the browser being used. Chrome might use more computer resources for the various other things it is doing in the background. You might have had more tabs open in Chrome, or more applications running at the same time. Background processes on the computer might have been using more computer resources at that time. To get a more accurate answer, you would need to run the program multiple times on each browser at various times to see whether or not the browser is actually the reason the script runs slower/faster.
  Comment on KLaudano's post “There are a variety of po...”
  (2 votes)
Leonard Wang
Posted 4 years ago. Direct link to Leonard Wang's post “I am confused by the thir...”
I am confused by the third javascript code, can you give some explanations about those javascript? Thanks for your work!
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Martin
  Posted 4 years ago. Direct link to Martin's post “The first function is the...”
  The first function is the searchList() function that's being analyzed.
  The second function is the tester. In the first step a sorted list is created and in the next step a random number is selected for search and then the search is performed a couple of thousand times in order to get the average run time in nanoseconds.
  The code is already pretty well documented, could you be a little more precise about which part confuses you?
  Comment on Martin's post “The first function is the...”
  (2 votes)
PrasharJaagat1
Posted 3 years ago. Direct link to PrasharJaagat1's post “Is there a way of calcula...”
Is there a way of calculating the number of binary search operations that will be required given a list size?
Button navigates to signup pageButton navigates to signup page
(0 votes)
Answer
- KLaudano
  Posted 3 years ago. Direct link to KLaudano's post “Suppose we have a sorted ...”
  Suppose we have a sorted array of size N.
  
  Maximum Number of Comparisons Using Binary Search Algorithm = 1 + ceiling(log_2(N))
  Button navigates to signup page
  (2 votes)