### Math 2320 -- Quiz 1 D -- Dow -- September 30, 2:00

1. (4marks) Using the definition of "f(n) is O(g(n))"
show that " if f(n) is O(3n^2+16) then f(n) is O(n^2) .

(2marks) for somehow stating the definition of "f(n) is O(g(n)) " being sure to mention C and k.
From the definition, we've got that
|f(n)| < C*(3n^2+16) for all n > k for some C and k.

(1mark) Then we just note that 3n^2+16 < 4 n^2 for all n> 4 (or some such similar thing).

(1mark) Hence, |f(n)| < C'* n^2 for all n> k' where C'=4C and k' is bigger than both k and 4 (or whatever value you used above).

2. State whether this is True or False ?
If f(n) is O(n^2) then f(100) is bigger than f(10) .

If true, give an example. If false, give a counterexample.

It is false, f(n) being the constant function 1 or some used f(n)=1/n are counterexamples.

1. 2. In the following algorithm t will count the number of critical steps.
Procedure Sum_of_2 (x,a_1,a_2,...,a_n; n integers)
t:=1 { this is our counting device}}
i:=1
while i <= n
begin
j:=i { j starts at i }
t:=t+1 { t {\rm is just the counter }}
while a_i+a_j <> x and j <= n
begin
t:=t+1 { t is just the counter }
j:=j+1
end { end the while}
if j <= n { test if they were equal }
then i:=n+2 { make i large if x=a_i+a_j }
else i:=i+1 { usual increment otherwise }
t:=t+2 { increment counter (by 2 to see if you're watching)}
end {the i loop ends here}
{ i is n+2 if x was equal to some a_i+a_j }
(a) What is the value of the counter t as a function of n in the worst case? [A sum of terms is an acceptable answer for part (a).]

(2marks) for some reasonable looking sum that showed that you analyzed the algorithm for each value of i as i runs from 1 to n.

Considering some fixed i between 1 and n, we see that j starts at i and runs up to potentially n, hence j runs through n-i+1 values.

What happens to t while all this is going on? Well, for each i, we increment t by 1 before we start the j loop and increment it by 2 when we finish the j loop. During the j loop, we increment by 1 for each value of j, Hence 3+(n-i+1) times.