1. Proove n^2 is O(n 3 /2000 ) -> choose witneses. c and k 2. Prove 2 n+1 is O(n

Question

1. Proove n^2 is O(n3/2000) -> choose witneses. c and k

2. Prove 2n+1 is O(n2) -> choose witneses c and k

3. Proove 2n is O(3n/1000) -> choose witneses c and k

4. For what values N is 10NlogN > 2N2

5.There exist an algorithm with best, worst and average case runtimes are all O(2n) and this bound is tight. I have determined that I can solve a problem of size K in time t with this algorithm. Approximately how large a problem (in terms of K) should I be able to solve in 2t time units? How about if I have O(log(n)) algorithm ?

Explanation / Answer

To prove that n2=O(n3/2000), we need to find witness c and k such that n2<k(n3/2000) for all n>=c

Suppose n=1 and k=4000

LHS=1

RHS=4000*(1/2000)=2

1<2 Therfore the inequality holds for n=1 and k=4000

Suppose n=2

LHS=(2)2=4

RHS=4000*(23/2000)=2*8=16

4<=16

Therefore the inequality proves for c=1 and k=4000

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.