Deck 15: Running Time Analysis

Question 1

Which of the following is the Big-Oh of this function: T(n) = n + (2n + 8)?

A) O(1)
B) O(n)
C) O(n²)
D) O(n log n)

Answer 1

B

Question 2

What is a handwaving method?

A) An estimation method for evaluating the dominant term
B) A method involving iterating several times until we can identify a pattern
C) A method of guessing the value of T1(n) as a function of n and then checking to see if the guess is correct
D) A Master Theorem based on strict mathematics

Answer 2

A

Question 3

It has become common in the industry to say Big-Oh instead of Big-Theta.

Answer 3

True

Question 4

For n = 1,000, Bubble Sort executes more statements than Merge Sort, which executes more statements than Sequential Search, which executes more statements than __________.

Question 5

Between Sequential Search or Binary Search, which one will execute more statements when searching an array of a million users for a particular user name?

Question 6

If n = 10 and the order of magnitude is n², how many statements will be executed?

Question 7

Most programmers tend to disregard ____________ when writing code.

A) software requirements
B) hardware specifications
C) memory utilization issues
D) exploding cost of memory

Question 8

Which of the following has the lowest order of magnitude?

A) n log n
B) n
C) n²
D) log n

Question 9

When programming, you want as tight an upper bound as possible.

Question 10

Algorithms with n as the exponent of the function should always be the first choice, as the running time will be better.

Question 11

It is necessary to know exactly how many statements are executed in order to determine the Big-Oh running time of the function.

Question 12

Which of the following will result in the shortest running time?

A) 3ⁿ = 3 * 3^{n - 1}
B) 3ⁿ = 2(3^{n - 1}) + 3^{n - 1}
C) 3ⁿ = 3^{n - 1} + 3^{n - 1} + 3^{n - 1}
D) Each will produce the same result, so the running time is the same.

Question 13

When trying to develop and identify a pattern using iteration, which of the following is the best strategy?

A) Precisely compute all terms.
B) Leave terms as patterns.
C) Use exponents as much as possible.
D) Use handwaving to get a precise result.

Question 14

Inefficient coding will increase the running time, possibly significantly.

Question 15

Using the following code segment could help identify whether the program is running efficiently by counting the number of statement executions.
int counter = 0;
int temp, indexOfMax = 0;
for ( int i = 0; i < arr.length - 1; i++ )
{
indexOfMax = 0;
animate( i, 0, counter );
…

Question 16

What is the Big-Oh of the function T(n) = n² - 2n + 81?

A) O(1)
B) O(n)
C) O(n²)
D) O(n log n)

Question 17

Merge Sort is more efficient than Bubble Sort because Merge Sort is O(n²) and Bubble Sort is O(n log n).

Question 18

If the order of magnitude is n² and n = 5, ____ statements will be executed.

A) 10
B) 25
C) 32
D) None of these is correct.

Question 19

If the order of magnitude is log n and n = 1 million, __________ statements will be executed.

A) 10
B) 2.23
C) approximately 1 million
D) approximately 20

Question 20

A function f (n) is Big-Theta of another function g(n) if and only if:

A) f(n) is Big-Omega of g(n) and f(n) is Big-Oh of g(n).
B) f(n) is Big-Omega of g(n) and g(n) is Big-Oh of f(n).
C) for any n <= n1, f (n) <= c1 * g(n), and for any n <= n2, f (n) <= c2 * g(n).
D) for any n >= n1, f (n) <= c1 * g(n), and for any n <= n2, f (n) >= c2 * g(n).

Question 21

The pattern T(n) = 2^k T(n / 2^k) + kn is:

A) O(n)
B) O(log n)
C) O(n log n)
D) O(n²)

Question 22

In trying to compute running time, we are interested in:

A) relative time.
B) absolute time.
C) a precise mathematical expression.
D) All of these are correct.

Question 23

Running times represented using the Big-Oh notation are interested in:

A) an upper-bound running time.
B) as tight an upper bound as possible.
C) a condition such that for an n sufficiently big, the expression inside Big-Oh is a lower bound of the running time.
D) All of these are correct.

Question 24

Which of the following is the Big-Oh of this function: T(n) = T(n / 2^k) + 5 * k?

A) O(log n)
B) O(n)
C) O(n²)
D) O(n log n)

Question 25

To analyze the running time of a code sequence or a method, you can count the number of times each statement is executed and calculate a total count of statement executions.

Question 26

Merge Sort and Quick Sort are two sorting algorithms implemented recursively.

Question 27

The strategy we use to compute the running time of a method where we start with a recurrence relation and we iterate several times to develop a pattern is known as __________.

Question 28

A function has the running time T( n ) = 4 n³ − 6 n² + 7 n + 9. What is its running time in Big-Oh notation?

A) O( 1 )
B) O( n )
C) O( n² )
D) O( n³ )

Question 29

What is the typical running time of a single loop with a counting variable going from 0 to n − 1?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 30

What is the typical running time of a double loop with a counting variable going from 0 to n − 1 for both the outer loop and the inner loop?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 31

What is the typical running time of a single comparison using an if statement?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 32

What is the average running time of a sequential search when searching a single-dimensional array of size n?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 33

What is the best-case running time of sequential search when searching a single-dimensional array of size n?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 34

What is the running time of a method with the following recurrence relation: T( n ) = T( n − 1 ) + T( n − 1 ), with T( 0 ) = 1?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 35

What is the running time of a method with the following recurrence relation: T( n ) = T( n − 1 ) + 1, with T( 0 ) = 1?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 36

What is the running time of a method with the following recurrence relation: T( n ) = T( n − 1 ) + 2, with T( 0 ) = 1?

A) O( n )
B) O( 2ⁿ )
C) O( 1 )
D) O( n² )

Question 37

What is the average-case running time of binary search when searching a single-dimensional sorted array of size n?

A) O( n )
B) O( log n )
C) O( 1 )
D) O( n² )

Question 38

What is the best-case running time of binary search when searching a single-dimensional sorted array of size n?

A) O( n )
B) O( log n )
C) O( 1 )
D) O( n² )

Question 39

What is the average-case running time of insertion sort, bubble sort, and selection sort when sorting a single-dimensional array of size n?

A) O( n )
B) O( log n )
C) O( 1 )
D) O( n² )

Question 40

What is the average-case running time of merge sort when sorting a single-dimensional array of size n?

A) O( n² log n )
B) O( 2ⁿ )
C) O( n log n )
D) O( n² )

Question 41

What is the best-case running time of merge sort when searching a single-dimensional array of size n?

A) O( n² log n )
B) O( n )
C) O( n log n )
D) O( n² )

Question 42

In terms of Big-Oh notation, a running time of 2n is equivalent to a running time of n.

Question 43

The running time of a recursive method is always better than the running time of a non-recursive method.

Question 44

The running time of a method is always the same no matter how that method is coded.

Question 45

When we measure the speed performance of an algorithm, we use the expression __________.

Question 46

Compare the running times of these two statements. Justify your answer.
T(n) = 2 + (3 * n + 2) + (n² - 2)
T(n) = 2 + (3 + n + 2) + (n - 2)

Question 47

Evaluate whether the following code is efficient. If not, recommend a better code.
return powerOf2B( n - 1 ) + powerOf2B( n - 1 );

Question 48

Analyze whether you should be more concerned about the best-case scenario or the worst-case scenario when determining which algorithm to use.

Question 49

How does the while loop execution in Insertion Sort show that it is going to have a longer running time than Merge Sort?

Question 50

Explain why it is increasingly important for programs to be efficient.

Question 51

Identify what must be changed to make the following a true statement: Algorithms that have a running time where n is the logarithm of the function, such as log n, take a very large number of statement executions and are very slow; they should be used only if no better algorithm can be found.

Question 52

Evaluate why the somewhat-complex rules for Big-Oh can be simplified into keeping only the dominant term and ignoring its coefficient.

Question 53

Identify the dominant term and Big-Oh for the following:
4 * n * log n + 8 * n + log n + 16

Question 54

Identify the dominant term and the Big-Oh for the following: 5 * n + 287

Question 55

Andre runs an Insertion Sort and a Bubble Sort, using the same data, on the same computer. Estimate if one will have the shorter running time. Why do you think it is necessary to specify that the same computer is used to implement both algorithms?

Question 56

In the following code, identify the first and second base case, and evaluate whether this code would have an efficient running time.
1 public static int recursiveBinarySearch
2 ( int [ ] arr, int key, int start, int end )
3 {
4 if ( start <= end )
5 {
6 int middle = ( start + end ) / 2;
7 if ( arr[middle] == key )
8 return middle;
9 else if ( arr[middle] > key )
10 return recursiveBinarySearch( arr, key, start, middle - 1 );
12 else
13 return recursiveBinarySearch( arr, key, middle + 1, end );
14 }
15 else
16 return -1;
17 }