Efficiency of Algorithms - Part 2

Question 1

What do data structure courses actually mean when they say Big-O?

Answer 1

Big-Ø

Question 2

Big-Omega is essentially the ____ of Big-O

Answer 2

opposite

Question 3

big-omega defines a ___ ___

Answer 3

partial order

Question 4

What is the difference in the definitions of Big -O and Big-Omega?

Answer 4

where we had f of n less than or equal to g of n before, we now have f of n greater than or equal to g of n.

Question 5

T/F: Big-Theta is defined using both Big-O and Big-Omega

Answer 5

True

Question 6

Big-Theta is the ____ of Big-Omega and Big-O

Answer 6

intersection

Question 7

Why isn’t Big-O unique?

Answer 7

it is just an ordering

Question 8

Rather than ___ ___ Big-Theta defines an ___ ___

Answer 8

partial order

equivalence relation

Question 9

What does an equivalence relation mean?

Answer 9

when some function f is in Big-Theta of g, both functions grow at the same rate

Question 10

When do we say that f and g are equivalent?

Answer 10

When Big-Theta of f is equal to Big-Theta of g

Question 11

T/F: n and 2n are equal according to Big-Theta.

Answer 11

True

Question 12

T/F: n and n² are equal according to Big-Theta

Answer 12

False. not equal

Question 13

Big-Theta groups functions into ____ ____

Answer 13

equivalence classes

Question 14

What do all members of an equivalence class have in common?

Answer 14

They grow at the same rate

Question 15

list the axioms required for a relation to be an equivalence relation

Answer 15

reflexive

Symmetric

Transitive

Question 16

define the Symmetric axiom

Answer 16

when x is equal to y y is equal to x

Question 17

What do equivalence relations do to sets?

Answer 17

partition them into equivalence classes

Question 18

list 2 equivalence relations

Answer 18

modulo 4

equality of fractions

Question 19

What resources are we interested in measuring the efficiency of?

Answer 19

CPU time

Memory

Question 20

what technique did we use to figure out CPU time?

Answer 20

counting lines of code

Question 21

T/F: In many cases, the memory requirements are constant.

Answer 21

True

Question 22

One of which two program features need to be present for the memory requirements to be more than constant?

Answer 22

dynamic allocation of memory

recursion

Question 23

Why does recursion need more memory?

Answer 23

It uses increasing amounts of the compiler’s run-time stack as the depth of recursion increases

Question 24

How can we determine the complexity of a problem?

Answer 24

considering the most efficient known algorithms for solving a particular problem

Question 25

What are intractable problems?

Answer 25

problems for which all known algorithms require more than polynomial time. the are amount the most difficult solvable problems.