CS2303 Tutorial Week 4 Notes:
Mathematical Preparations:
(Optional) Proof Methods:
To prove correctness: Proof by Induction
Base case (initialization): Property holds when n=1
Induction Step (maintenance): if Property holds for n=k, then Property holds for n=k+1 (k>1)
Example: In Insertion Sort, when we are looking at the kth number, the first k-1 numbers are sorted
Base case : when we are looking at the 2nd number, the first number is sorted
Induction Step: if the first k-1 numbers are sorted, when we are dealing with the kth number, we will move it to the correct place so that the first k numbers will be sorted. Therefore, when we are looking at the (k+1)th number, the first k numbers will be sorted.
Termination: when we are looking at the (n+1)th number which does not exist, the first n numbers are sorted.
To prove incorrectness: Proof by Counter Example
Example: Prove that n
A: O( ) works in the following way: We have n2≤n2, 3n<3n2, 1
A: All the asymptotic notations compare function values for sufficiently large input size. In your example, when n>20, we can know that n4<2n.
What’s the difference between Θ and o?
For Θ, if f(n)= Θ(g(n)), then we can find a positive number c so that the value of g(n) will never exceeds cf(n).
For o, if f(n)= o(g(n)), then for any positive number c, as n increases, g(n) can be larger than cf(n). For example, we know n=o(n2), then it is true that n2>10n when n>10; n2>100n when n>100; n2>1000n when n>1000; … So we can see that n is really better than n2. In fact, o means the value of f(n)/g(n) will approach 0 if n keeps growing.
CS2303 Tutorial 4 Exercises
1. Do Big-Oh Analysis for the following functions:
(a) T(n)=2n3+700nlogn+6
(b) T(n)=4logn+100n+2
(a) T(n)=O(n3)
(b) T(n)=O(n)
2. Suppose program 1 has worst case running time T1(n)=3n2+100nlogn+9, program 2 has worst case running time T2(n)=2n+n and they can output the same results. Which program do you choose? Explain the reasons for the choice.
We will choose T1(n). It’s because T1(n) = O(n2) ,T2(n) = O(2n). n2 grows slower than 2n, we can see that the running time of T2(n) is larger than T2(n) when the input size is large.
3. Suppose program 1 has best case running time T1(n)=3n2, program 2 has best case running time T2(n)= n and they can output the same results. Which program do you choose? Explain the reasons for your answer.
We can not decide which program is better simply by looking at the best case running time. We need the worst case running time to do the comparison.
4. You are given a task to find whether the first word of a paragraph appears at least twice in the paragraph, and you decide to write a program to scan the word one by one from the very beginning of the text. What’s the worst case for your program? Describe the situation.
The worst case is: The second occurrence of the first word is the last word in the text file or the first word only appears once.
5. Analyze the running time of the following program:
(a) Void function1(int n)
{
int i,j;
int x=0;
for(i=0;i
x–;
else
for(j=0;j