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

Question

This problem is on determining whether one function is Big-O 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, c f(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 O(2^n)? (log^2 n denotes log n times log n) Is 2^2n+1 element O(2^2n)? Is 2 squareroot n element O ((2^n)^1/log n)?

Explanation / Answer

Answer:

n^3 represents function's worst case complexity , the big O is taken a term with highest power of n , therefore O(n^3) is its worst case time.

Here inorder to check whether the statement is true , we check both the functions on higher values of n

n = 16

then logn^loglogn = 4^2 = 16

2^(2) = 4

lets check at n = 128

logn^loglogn = 7^3 = 128

2^logn^1/2 = 2^7^1/2 < 128

Thus logn^loglogn is comming greater than 2^log^1/2 , therefore the statement : logn^loglogn = O(2^logn^1/2) is FALSE.

taking log on both sides

log(n^log^2n) = log(2^2n)

log^2n * logn = 2nlog2

if we can see that log^2n * logn will be greater than 2^2n

Hence n^log^2n is O(2^2n) is FALSE

It is true always because for big O notation we take the term with highest power of n.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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