Meliora
by induction.Induction on n.
Basis: n=1,![]()
Induction: Assuming
we show 

Substituting the induction hypothesis

Basis: P(1)
: == 8-1 == 7 and 7|7
Induction: Assume: P(n): 7|
so
or
for some m
Show:
![]()
![]()
![]()
==![]()
==![]()
S(n): "n³8,$ integers x,y Ž n == 5x+3y
Basis: Must prove 3 basis cases
S(8): 8 = 5(1)+3(1),
S(9): 9 = 5(0)+3(3),
S(10): 10 = 5(2)+3(0)
Induction: S(n+1), assume(via basis) (n+1)³11, So, ((n+1)-3)==(n-2) ³ 8 .
Assume(BTIH); S(n-2): (n-2) = 5a+3b
Therefore (n-2)+3= 5a+3b+3
Or (n+1) = 5a+2(b+1)
c=9
9n2 > n2+4n+4, 9>1+4/n+4/n2
n0=2
5n2>(n+2)2
5n2>(n2+4n+4)
5>1+4/n+4/n2
For Q6-Q8, tell whether the stated big-oh relationship holds. If it does not, you can just say “false”. If the relationship does hold, then you must give witnesses n0 and c.
Ans: n0=1;c=57. There are many other choices. However, most people who tried something else lost points because they forgot that there is no requirement that c be an integer. Since we were looking for the least c for a given n0, if you, say picked n0=12, you had to say c = 134/144, not c =1
Ans: n0=10, c=1
Ans: n0=0,c=1
n2+n4 > 2n3
1+1/n2 > 2/n
public int A(int n){
If (n >=3) return (A(n-1) + A(n-3));
else If (n<0) return –A(-n);
else if (n ==0) return 0;
else if (n <= 2) return 1;
}
Give the run time O(n) for the following code samples
for (int i=0;i<n;i++) {
inc *= 2 ;
if (inc >= n) return;
for (int j=0;j<n;j += inc)
x++;
}
Ans: N/2+N/4+… , so O(n)
for(int i=0;i<n;i++) {
inc++;
for (int j=0;j<n;j+=inc)
x++;
}
Ans: N+N/2+N/3+…, so O(NlogN)
for(int j =0; j<n*n*n;j++)
x++;
Ans: O(N6)
For Q13-Q14, assume the following node class
class Node {
public int i;
public Node next;
}
public static Node insert(list, int val) {
Node temp;
if (list == null) {
temp = new Node();
temp.i = val;
temp.next = null;
Return temp;
} else
if (list.i < val) {
list.next = insert(list.next,val);
return list;
} else {
temp = new Node();
temp.i = val;
temp.next = list.next;
list.next = temp;
return list;
}
}
public static Node revList(Node n) {
if (n.next == null) return n;
Node temp = delLast(n);
temp.next = revList(n);
return temp;
}
public static Node delLast(Node n) {
Node temp = n ;
Node temp2 = null;
if (temp == null) return null;
else if (temp.next == null) { return n; }
else if ((temp.next).next == null) {
temp2 = temp.next;
temp.next = null;
return temp2;
} else return delLast(temp.next);
}
For Q-Q, consider the recurrenc:
Basis: T(1) = 0
Induction:
for integers > 1
T(1)=0,T(2)=1,T(3)=1.5,T(4)=1.75,T(5)=1.875
T(n)=(T(n-2)/4)+3/2
T(n)=(T(n-3)/8)+7/4
![]()
I==(n-1) because T(n-(n-1))==T(1) = 0
![]()