Design, Analysis, Implementation

Question 1

Big-O notation

Answer 1

Given two functions T(n) and f(n), that always return positive numbers,

T(n) ∈ O( f(n) )

if and only if there exist constants
c, n₀ > 0

such that,
for all n≥n₀,

T(n)≤cf(n)

Question 2

5 Big-O Simplification Rules

Answer 2

• Constant multiple rule
• Domination rule
• Addition rule
• Multiplication rule
• Transitivity rule

Question 3

Constant multiple rule

Answer 3

If T(n) ∈ O( f(n) )
and c>0,

then

T(n) ∈ O( c ∗ g(n) )

Question 4

Domination rule

Answer 4

If T(n) ∈ O( f(n)+g(n) )
and
f(n) ∈ O( g(n) )

then

T(n) ∈ O( g(n) )

We say that g “dominates” f

Question 5

Addition rule

Answer 5

If
T₁(n) ∈ O( f(n) )
and
T₂(n) ∈ O( g(n) )

then
T₁(n) + T₂(n) ∈ O( f(n) + g(n) ).

Question 6

Multiplication rule

Answer 6

If
T₁(n) ∈ O( f(n) )
and
T₂(n)∈O( g(n) )

then
T₁(n) ∗ T₂(n) ∈ O( f(n)∗g(n) )

Question 7

Transitivity Rule

Answer 7

If
T(n) ∈ O( f(n) )
and
f(n) ∈ O( g(n) )

then
T(n) ∈ O( g(n) )

Question 8

Loop invariant

Answer 8

A property which is preserved at every iteration through the loop.

Question 9

3 Steps to showing a loop invariant

Answer 9

1. Initialization: The invariant is true at the beginning of the first iteration.
2. Maintenance. If the invariant is true at the beginning of one iteration, it’s also true at the beginning of the next iteration.
3. Termination. After the loop exists, the invariant PLUS the loop termination condition tells us something useful.

Question 10

Big-Ω

Answer 10

T(n) ∈ Ω( f(n) )
if and only if
f(n) ∈ O( T(n) )

Question 11

Big-Θ

Answer 11

T₁(n) ∈ Θ( T₂(n) )
if and only if both

T₁(n) ∈ O( T₂(n) ) and T₂(n) ∈ O( T₁(n) ).