WEEK 2: ALGORITHM EFFICIENCY

Question 1

a loop that does a fixed number of operations n times is ____

Answer 1

O(n)

Question 2

this is the maximum number of operations for inputs of a given size

Answer 2

worst-case

Question 3

this is the average number of operations for inputs of a given size

Answer 3

average-case

Question 4

this is the fewest number of operations for inputs of given size

Answer 4

best-case

Question 5

2 types of complexity analysis used to assess the efficiency of algorithms

Answer 5

computational complexity, asymptotic complexity

Question 6

measure of how much effort is needed to apply an algorithm, or how much it costs

Answer 6

computational complexity

Question 7

these are the 2 factors measured in complexity analysis

Answer 7

time and space

Question 8

computational complexity is dependent in these 2 aspects

Answer 8

platform/system dependent & language dependent

Question 9

true or false: comparing algorithms can be done on different machines or different programming languages

Answer 9

false

Question 10

true or false: when comparing algorithm efficiencies, real-time units such as microseconds and nanoseconds are to be used

Answer 10

false

Question 11

true or false: in comparing algorithm efficiencies, logical units representing the relation ship between ‘n’ the size of the file, and ‘t’ the time taken to process the data should be used

Answer 11

true

Question 12

if t = cn, then an increase in the size of data increases the execution by the same factor

Answer 12

linear relationship

Question 13

in mathematics, this is the power to which a base, such as 10, must be raised to produce a given number

Answer 13

logarithm n

Question 14

if t = log2n, then doubling the size ‘n’ increases ‘t’ by one time unit

Answer 14

logarithmic relationship

Question 15

in linear relationships, if t=cn, then an increase in the size of data increases the execution time by _________

Answer 15

the same factor

Question 16

in logarithmic relationships, if n = log2n, then doubling the size ‘n’ increases ‘t’ by ______

Answer 16

one time unit

Question 17

true or false: any terms that do not significantly affect the outcome of a function cannot be eliminated

Answer 17

false

Question 18

any terms which don’t significantly affect the outcome of the function can be eliminated, producing a function that approximates the functions efficiency. this is called ___________

Answer 18

asymptotic complexity

Question 19

this is a part of the theory of computation dealing with the resources required during computation to solve a given problem

Answer 19

complexity theory

Question 20

how many steps it takes to solve a problem

Answer 20

time

Question 21

how much memory it takes to solve a problem

Answer 21

space

Question 22

another resource that can be considered in asymptotic complexity

Answer 22

how many parallel processors are needed to solve a problem in parallel

Question 23

this is used to give an asymptotic upper bound for a function, i.e. an approximation of the upper bound of a function which is difficult to formulate

Answer 23

big-o notation

Question 24

this is the lower bound equivalent of the big-O notation

Answer 24

big-Ω (omega notation)

Question 25

this denotes the number of steps an algorithm requires to solce a specific problem

Answer 25

runninng time

Question 26

in general, the running time of an algorithm depends on these 2 factors

Answer 26

size of the problem, repsective input

Question 27

this represents tight bound

Answer 27

Θ(n)

Question 28

complexity where the there is a constant number of operations, not depending on the input data size

Answer 28

constant - O(1)

Question 29

complexity where the number of operations proportional of log2n where n is the size of the input

Answer 29

logarithmic - O(logn)

Question 30

complexity where the number of operations is proportional to the input data size

Answer 30

linear - O(n)

Question 31

in this complexity, the number of operations is proportional to the square of the size of the input data

Answer 31

quadratic - O(n^2)

Question 32

in this complexity, the number of operations is proportional to the cube of the size of the input data

Answer 32

cubic - O(n^3)

Question 33

in this complexity, there is an exponential number of operations; fast growing

Answer 33

exponential - O(2^n), O(k^n), O(n!)

Question 34

if a program takes a lot of time, you can still run it, and just wait longer for a result. however, if a program takes a lot of _______, you may not be able to run it at all.

Answer 34

memory

Question 35

for this, space complexity is usually just a matter of looking at the variable declarations and storage allocation calls

Answer 35

iterative program

Question 36

analysis of this type of program is more complicated; the space used at any time is the total space used by all recursive calls active at that time

Answer 36

recursive program

Question 37

true or false: in recursive program space complexity, each recursicve call takes a quadratic amount of space

Answer 37

false; constant

Question 38

generally defined as a function of the number of elements being processed and the type of loop being used

Answer 38

algorithm efficiency, f(n)

Question 39

true or false: calculating the average case complexity is easier than calculating approximations in the form of big-O, big-Ω, and big-Θ

Answer 39

false; average-case is difficult