Ch3: Growth of Functions

Question 1

Asymptotic efficiency of an algorithm

Answer 1

How the running time of the algorithm increases as the size of the input increases without bound

Question 2

Asymptotic notation actually applies to…

Answer 2

mathematical functions (e.g. f(n) = an^2 + bn + c)

Question 3

Asymptotic notation usually applies to…

Answer 3

functions that characterize the running times of algorithms

Question 4

Asymptotic notation can also be applied to…

Answer 4

functions that characterize the space used by an algorithm (or any other function having nothing to do with algorithms!)

Question 5

A function f(n) belongs to Big-Theta(g(n)) if…

Answer 5

…there exist positive constants c1 and c2 such that it can be sandwiched between c1*g(n) and c2*g(n) for sufficiently large n

Question 6

This means…?

Answer 6

f(n) is equal to g(n) within a constant factor

Question 7

If f(n) = Big-Theta(g(n)), g(n) is a…

Answer 7

asymptotically tight bound for f(n)

Question 8

If f(n) = Big-O(g(n)), g(n) is a…

Answer 8

asymptotic upper bound for f(n)

Question 9

This means…?

Answer 9

g(n) is an upper bound on f(n) to within a constant factor

Question 10

Big-Theta implies

Answer 10

Big-O and Big-Omega

Question 11

When we use Big-O on the worst-case running time, we have…

Answer 11

a bound on the running time of the algorithm on every input

Question 12

If f(n) = Big-Omega(g(n)), g(n) is a…

Answer 12

asymptotic lower bound for f(n)

Question 13

When we say the running time of an algorithm is Big-Omega(g(n)), we are…

Answer 13

giving a lower bound on the best-case running time of an algorithm

Question 14

When asymptotic notation appears in a formula, in general we interpret it as…

Answer 14

standing for some anonymous function we don’t care to name (e.g. 2n^2 + O(n))

Question 15

Asymptotically tight (definition)

Answer 15

Big-Theta is the definition of an asymptotically tight bound

Question 16

Asymptotically tight (intuition)

Answer 16

Asymptotically tight is analogous to saying “is equal to”. Or like =, >=, and <= versus a strict > or

Question 17

Which bounds are asymptotically tight?

Answer 17

Big-O, Big-Omega, Big-Theta. Only Big-Theta is purely asymptotically tight, while the others can be asymptotically tight upper and lower bounds.

Question 18

Big-O and Big-Omega can be asymptotically tight because…

Answer 18

they are bounds that can be equal to f(n) within a constant factor

Question 19

Little-o and Little-omega are not asymptotically tight because…

Answer 19

They cannot be equal to f(n) within a constant factor (like > and

Question 20

Little-o means…

Answer 20

The o() function grows much faster as n increases to infinity (Little-o is an > upper bound)

Question 21

Little-omega means…

Answer 21

The omega() function becomes insignificant as n increases to infinity (Little-omega is a < lower bound)

Question 22

f(n) = o(g(n)) implies

Answer 22

lim f/g = 0 (as n increases to infinity)

Question 23

f(n) = omega(g(n)) implies

Answer 23

lim f/g = infinity (as n increases to infinity)

Question 24

Are all functions asymptotically comparable?

Answer 24

No, some functions have a limit that is undefined (vertical asymptotes, oscillation, etc.)

Question 25

lg(f) = o(lg(g)) implies what about f and g?

Answer 25

f = o(g)

Question 26

f = o(g) implies what about lg() of both?

Answer 26

Nothing!

Question 27

Definition of Big-Theta(g(n))

Answer 27

Question 28

Definition of Big-O(g(n))

Answer 28

Question 29

Definition of Big-Omega(g(n))

Answer 29

Question 30

Definition of Little-o(g(n))

Answer 30

Question 31

Definition of Little-omega(g(n))

Answer 31