This problem is on determining whether one function is Big-0 of the other. Provi

Question

This problem is on determining whether one function is Big-0 of the other. Provide a proof for your answers. If you are showing that if f Element O(g), then you must show that there is a constant c > 0 such that for every n, cf(n) lessthanorequalto g(n). Your proof must state the value of the constant c. If you are showing that f NotElement O(g), then you must show the for every constant c > 0 it is not the case that cf(n) lessthanorequalto g(n). In your proofs, you may use the fact that for every k, a > 0, n^k Element O(n^k+a), and log n Element O(n^a). Is 25n^3 - 46n^2 Element O(n^3)? Is log n^log log n Element O(2 Squareroot log n)? Is n^log^2 n Element 0(2^n)? (log^2 n denotes log n times log n) Is 2^2^n + 1 Element 0(2^2^n)?

Explanation / Answer

1)

To prove 25n^3-46n^2 is O(n^3), according to the given definition, we need to find a positive value c >0 such that

c*(25n^3-46n^2) <=(n^3), for every c>0 n0>=n

C*(25n^3-46n^2) <= (n^3)

=>(n^3) –c*25n^3+c*46n^2 >= 0

=> (1 –25*c)n^3+c*46n^2 >= 0

=> (1-25*c) >= 0

=> (25*c) <= 1

=> c <= 1/25

=> c<=0.04

Therefore, 25n^3-46n^2 is O(n^3), for c=0.04

2)

To prove log n^log log n is O(2^sqrt(log n)) , according to the given definition, we need to find a positive value c >0 such that

c*(log n^log log n) <= 2^sqrt(log n)

c <= ((log n^log log n))/(2^sqrt(log n))

But let n=1, then the above value becomes c<=infinity

But the c value must be greater than 0.

Therefore, log n^log log n is not O(2^sqrt(log n))

3)

To prove n^log^2 n is O(2^n) , according to the given definition, we need to find a positive value c >0 such that

c*(n^log^2 n) <= 2^n

=> c<= (2^n / (n^log^2 n))

Let n=1, then c<=2. Thus , Assume c=1

Therefore, n^log^2 n is O(2^n)) for c=1

4)

To prove 2^(2^n+1) is O(2^(2^n)), according to the given definition, we need to find a positive value c>0 such that

c* 2^(2^n+1) <= 2^(2^n)

=> c <= (2^(2^n))/( 2^(2^n+1))

=> c <= 2^(-2^n)

Here 2^(-2^n) is unbound. Thus we can’t find the constant value c>0.

Therefore, 2^(2^n+1) is not O(2^(2^n))

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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