By Prof. Ruiz
Instructions
Solution:
In order to show that f(n)+g(n) = O(h(n)), we need to find constants k and n_{0} such that for all n ≥ n_{0}, f(n)+g(n) ≤ kh(n). Since f(n) = O(h(n)) and g(n) = O(h(n)) then by definition:Take k = k_{1} + k_{2}, and n_{0}= max(n_{1},n_{2}). Then
 ∃ k_{1} ∃ n_{1} ∀ n ≥ n_{1}, f(n) ≤ k_{1}h(n).
 ∃ k_{2} ∃ n_{2} ∀ n ≥ n_{2}, g(n) ≤ k_{2}h(n).
f(n)+g(n) ≤ k_{1}h(n) + k_{2}h(n) = (k_{1} + k_{2})h(n) = kh(n), for all n ≥ n_{0}.
Hence f(n)+g(n) = O(h(n)).
Solution:
Remember that 2^{2n} = 2^{n+n} = 2^{n}*2^{n}. Hence:
lim_{n→inf}(f(n)/g(n)) = lim_{n→inf}(2^{2n}/2^{n}) = lim_{n→inf}(2^{n}*2^{n}/2^{n}) = lim_{n→inf}(2^{n}) = infinity.
Therefore, by the theorem stated in class, f(n) = Ω(g(n)).
Input:
Output:
Algorithm: (See next page)
Instruction
Time taken per instruction
Number of iterations
{
stable := true . . . . . . . . . . . . . . . . . .
m := 1 . . . . . . . . . . . . . . . . . .
while stable AND m ≤ n do { . . . . . . . . . . . . .
w := 1 . . . . . . . . . . . . . . . . . . .
while stable AND w ≤ n do { . . . . . . . . . . . . . .
(* we'll check below if (m,w) is an unstable pair *)
if (InverseMenPrefer[m,w] < InverseMenPrefer[m,wife[m]])
AND
(InverseWomenPrefer[w,m] < InverseWomenPrefer[w,husband[w]]) . .
then {
stable := false . . . . . . . . . . . . .
}
w := w + 1 . . . . . . . . . . . . . . . . . . .
}
m := m + 1 . . . . . . . . . . . . . . . . . . .
}
return(stable) . . . . . . . . . . . . . . . . . . .
}
C_{1}
C_{2}
C_{3}
C_{4}
C_{5}
C_{6}
C_{7}
C_{8}
C_{9}
C_{10}
1
1




 
 
 
 
 n  n
times times
 
 
 
 
 
 


1
Solution:
Let's start by noting that the "if condition"(InverseMenPrefer[m,w] < InverseMenPrefer[m,wife[m]]) AND (InverseWomenPrefer[w,m] < InverseWomenPrefer[w,husband[w]])is true
if and only if man m prefers woman w over his wife and w prefers m over her husband
if and only if the pair (m,w) is unstable
if and only if the input perfect matching is unstable.Let's show now that the algorithm always outputs the correct answer for the given input perfect matching:
 If the input perfect matching is stable, then no unstable pair exists and hence the if condition is never true. Then, the variable "stable", which has been set to true at the beginning of the program, is never set to false, and the program correctly outputs "true".
 If the input perfect matching is unstable, then there is at least one unstable pair (m,w) that makes the if condition true. Then, the variable "stable" is set to false, stopping the iterations of both while loops, and making the program correctly output "false".
Solution:
T(n) = C_{1} + C_{2} + [C_{3} + C_{4} + [C_{5} + C_{6} + C_{7} + C_{8}]*n + C_{9}]*n + C_{10} = C' + [C'' + C'''*n]*n = C' + C''n + C'''n^{2} where: C' = C_{1} + C_{2} + C_{10} C'' = C_{3} + C_{4} + C_{9} C''' = C_{5} + C_{6} + C_{7} + C_{8}
Solution:
T(n) = C' + C''n + C'''n^{2}. Let g(n) = n^{2}.
In order to show that T(n) = Θ(g(n)) we need to find constants k_{1}, k_{2}, and n_{0} such that for all n ≥ n_{0}, k_{1}n^{2} ≤ T(n) ≤ k_{2}n^{2}.
Note that:Hence ∃ k_{1}=C''' ∃ k_{2}=(C'+ C''+ C''') ∃ n_{0}=max(0,1) ∀ n ≥ n_{0}, k_{1}g(n) ≤ T(n) ≤ k_{2}g(n). Therefore T(n) = Θ(g(n)).
 T(n) = C'+ C''n + C'''n^{2} ≤ C'n^{2} + C''n^{2} + C'''n^{2} = (C'+ C''+ C''') n^{2} = (C'+ C''+ C''') g(n), for all n ≥ 1, and
 T(n) = C'+ C''n + C'''n^{2} ≥ C'''n^{2} = C'''g(n), for all n ≥ 0.
Solution:
The perfect matching should be such that m_{1} and w_{1} (the 1st man and the 1st woman) form an unstable pair. For this particular case, the runtime of the algorithm would be:
T(n) = C_{1} + C_{2} + C_{3} + C_{4} + C_{5} + C_{6} + C_{7} + C_{8} + C_{9} + C_{10}, that constant.
Solution:
T(n) = C' + C''n + C'''n^{2}. Let h(n) = 1.
In order to show that T(n) = Ω(h(n)) we need to find constants k and n_{0} such that for all n ≥ n_{0}, T(n) ≥ k*1.
Note that: T(n) = C'+ C''n + C'''n^{2} ≥ 1 for all n ≥ 1. Hence ∃ k=1 ∃ n_{0}=1 ∀ n ≥ n_{0}, T(n) ≤ k*1. Therefore T(n) = Ω(h(n)).
Solution:
No. Let T_{A} and T_{B} be the runtime functions of algorithms A and B, respectively. By definition, of Θ, T_{A}(n) has the same growth rate as n^{2} for large enough n's (that is, for n ≥ n_{A} for some constant n_{A} ≥0), and T_{B}(n) has the same growth rate as n^{3} for large enough n's (that is, for n ≥ n_{B} for some constant n_{B} ≥0). But for some n_{0} < max(n_{A},n_{B}), it might happen that T_{A}(n_{0}) > T_{B}(n_{0}), and then B would be preferable to A on inputs of size n_{0}.
Solution:
Yes. Note that O(.) does not provide tight bounds. Take for example f(n)=n^{2}+n and g(n)=n. It is true for these functions that f(n)=O(n^{2}) and g(n)=O(n^{3}). Nevertheless, g(n) ≤ f(n) for all n, and hence an implementation of algorithm D can be more efficient than an implementation of algorithm C.