Deck 2: Analysis of Algorithms

Question 1

What is the order of the following growth function? t(n)= 5nlogn + 20n - 4

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

Answer 1

O(n log n)

Question 2

The following code segment has ______ time complexity?

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

Answer 2

O(nlogn)

Question 3

Which Growth function has the highest order?

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

Answer 3

O(2ⁿ)

Question 4

What is the time complexity of the following loop?

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

Question 5

Which of the following has the smallest time complexity?

A) 3n+5+2ⁿ
B) Log_n + 2
C) 3n+4
D) n log_n

Question 6

What does a growth function show?

A) How big a program must be before completed
B) How many times a program can be re used
C) Time or space utilization relative to the problem size
D) How many lines a program is

Question 7

Software must make efficient use of resources such as _______ and _______ .

A) Hard Drive, Video Card
B) CPU time, Memory
C) CPU time, Video Card
D) Memory, Hard Drive

Question 8

What is the O(_) of this growth function? ______
3n⁴+n²+3n-867.5309

Question 9

A __ function shows time or space utilization relative to the problem size.

Question 10

Algorithm ______ is a fundamental computer science topic.

Question 11

The ______ of an algorithm is found by eliminating constants and all but the
dominant term in the algorithm's growth function.

Question 12

The order of an algorithm provides an ______ to the algorithm's
growth function.

Question 13

If the algorithm is ______, a faster processor will not help in the long run.

Question 14

The time complexity of a loop is found by multiplying the complexity of the
______ by how many times the loop will execute.

Question 15

The analysis of nested loops must take into account both the ______.

Question 16

The order of an algorithm refers to the ______ of the algorithm's growth function.

Question 17

The order of an algorithm is found by eliminating constants and all but the dominant term in the algorithm's growth function.

Question 18

Speeding up the processor by a factor of 10 will increase the processing speed by a factor of 10 regardless of the efficiency of the algorithm.

Question 19

A growth function shows time or space utilization relative to the problem size.

Question 20

Software must make efficient use of resources such as CPU time and memory.

Question 21

The order of an algorithm provides a lower bound to the algorithm's growth function.

Question 22

If the algorithm is inefficient, a faster processor will help.

Question 23

The time complexity of a loop is found by multiplying the complexity of the body of the loop by how many times the loop will execute.

Question 24

The analysis of nested loops must take into account both the inner and outer loops.

Question 25

The order of an algorithm refers to the asymptotic complexity of the algorithm's growth function.

Question 26

Method calls are always O(n).

Question 27

What is the difference between the growth function of an algorithm and the order of that algorithm?

Question 28

Why does speeding up the CPU not necessarily speed up the process by the same amount?

Question 29

How do we use the growth function of an algorithm to determine its order?

Question 30

How do we determine the time complexity of a loop?

Question 31

How do we determine the time complexity of a method call?