(2marks) give the definition (in some form) of f(n) is O(g(n)), being sure to mention the C and the k.
(2marks) By definition, there are C,k such that
|f(n)| < C*(2n^2) for all n> k
Therefore if we use c=2C and keep k in the definition,
we get that
|f(n)|< c*|n^2| for all n> k
as required.
If f(n) is O(n^2) then n^2 is O(f(n)).
If true, give an example, if false, give a counterexample.
This is false, and f(n)=n is the kind of counter-example we'd expect (even f(n)=1 for all n works).
Procedure Divisors (n ; a positive integer)
d:=0 {d will count the number of divisors }
t:=0 { t is the counting device
for i:=1 to n
begin{d will be the number of positive integer divisors of n}
k:= i
while k+i < n { testing i}
beginif k+i=n then d:= d+1 { Check to see if i divides n }
k:=k+i { k increments by i }
t:= t+1 { t counts the number of basic steps }
end
end
(a) What is the value of the counter t as a function of n?
[A sum of terms is an acceptable answer for part (a).]
I expected something like:
Consider one by one, each value of i. i will go from 1
to n.
If i=1, then the next while loops exactly n-1
times.
If i=2, it loops [n/2]-1 times because k is
incrementing by 2's up to at most (n-1).
In general, for a fixed value of i,
the k while loop, runs [n/2]-1 times.
For values of i bigger than n/2 it doesn't loop at all.
Therefore we get the expression:
(n-1) + ([n/2]-1) + ... + ([n/i]-1) + ... + 0 + 0
We can add up the -1's, to get (n+[n/2]+[n/3]+...+[n/n])-n.
If you didn't catch the [n/i] idea, but at least realized it was no more than n-i (since the looping starts at i you still get full marks (carrying the "error").
(b) What is the time complexity, as calculated by t, in the worst case?
[If it arises, you can treat numbers like [x/5] as being equal to x/5.]
Well, they arose, the above simplifies to something like n*(1 + 1/2 + 1/3 + ... + 1/n) - n which is O(n log(n) )