(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).
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.
Procedure Sum_of_2 (x,a_1,a_2,...,a_n; n integers)(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).]
t:=1 { this is our counting device}}
i:=1
while i <= n
begin{ i is n+2 if x was equal to some a_i+a_j }
j:=i { j starts at i }
t:=t+1 { t {\rm is just the counter }}
while a_i+a_j <> x and j <= n
beginif j <= n { test if they were equal }
t:=t+1 { t is just the counter }
j:=j+1
end { end the while}
then i:=n+2 { make i large if x=a_i+a_j }t:=t+2 { increment counter (by 2 to see if you're watching)}
else i:=i+1 { usual increment otherwise }
end {the i loop ends here}
(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.
Answer: (3+n)+(3+(n-1))+(3+(n-2))+...+(3+(n-(n-1)))
or 3n + (n+(n-1)+(n-2)+...+2+1).
Marks: (1mark) for a reasonable looking sum, and (1mark) for having either the "n-i" or the " +2" show up.
(b) What is the time complexity, as calculated by t, in the worst case?
Of course that expression in Part (a) is O(n^2).