Category Archives: Test #1 Solutions

Give a big-O estimate for the number of operations (where an operation is an addition or a multiplication) used in this segment of an algorithm: for to     Explain your answer. Here there is one loop. In this loop, … Continue reading →

Give a big-O estimate for the number of operations (where an operation is an addition or multiplication) used in this segment of an algorithm: for to   for to     Explain your answer. There are two loops: the loop and the … Continue reading →

Let and be functions from the set of positive real numbers to the set of real numbers. Assume that is . Does it follow that is ? Explain your answer. The statement is not true. To show this, we just … Continue reading →

Use the definition of big- notation to determine whether is . To show that is , we would have to show that is and that is . However, we can see that is not , as follows: (This will be … Continue reading →

(a) Let and be functions from the set of positive integers to the set of real numbers. State the definition of the fact that is . We say that is if there exists a pair of positive constants such that, … Continue reading →

(a) Use pseudocode to describe an algorithm for finding the largest and second largest elements in a list of integers. procedure largest_and_2nd_largest if then     else     for to   if   then       else if   then return { is … Continue reading →

(a) Use pseudocode to describe an algorithm that takes a list of integers and finds the number of integers greater than 5 in the list. procedure greater_than_5 count:=0 for to     if     then count := count + … Continue reading →

(a) Describe in words how the binary search algorithm works: The binary search algorithm searches for the location of a number in an ordered list of numbers . It first finds the element in the middle of the list (or right … Continue reading →