Measuring an algorithm's efficiency

An online store manages an inventory of millions of products. On their front page, they show customers products related to the ones they've recently bought.

This procedure comes up with a list of similar products for a given list of products:

PROCEDURE findSimilarProducts(products) {
   similarProducts ← [] 
   FOR EACH product IN products {
     similarProduct ← calcSimilar(product)
     APPEND(similarProducts, similarProduct)
   }
   RETURN similarProducts
}

The calcSimilar() procedure takes 2 minutes to return a result, as it needs to do a complicated series of database lookups and mathematic operations. The other operations, creating the empty list and appending items to the list, only take a few nanoseconds.

If the store calls the procedure on a list of 5 products, approximately how long will it take to complete?

🤔

This code is written in pseudocode. You can't actually run pseudocode, but we use it for planning programs and for thinking about code independently of specific programming language.

AP CSP exam questions use pseudocode, so it's helpful to become familiar with it.

Here is a reference for the pseudocode used here:

PROCEDURE name (parameter1, parameter2, ...)
{
     <instructions>
     RETURN (expression)
}

A procedure called "name" that takes zero or more parameters. The procedure contains programming instructions and returns the value of expression.

a ← expression

Evaluates expression and assigns the result to the variable a.

list ← [value1, value2, value3]

Creates a list with 3 values. The first value is located at index 1, the second at index 2, the third at index 3.

APPEND(list, item)

Adds item to the end of list, increasing the length of list by 1.

FOR EACH value IN list
{
   <instructions>
}

Assigns value to the value of each element in list sequentially, starting from the first element and ending with the last element. Executes the code in instructions once for each value.

AP®︎/College Computer Science Principles

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

Problem