What are the Big-oh orders of the following growth functions? You should provide

Question

What are the Big-oh orders of the following growth functions? You should provide a relatively tight upper bound.

four different functions:

(a)f(n)=100 + 10log(base10)(n)n^2 + 45n

(b)nlog(base10)*(n) + nlog(base2) * (n)

(c)100c^3 + 4log(base2)(n)n + 450n, where c is not a function of n.

(d)f(n)=10e^(1/n) + 5n^2 + 100

(Question)Show the upper bound you give for f(n),above does indeed hold.

(d)Assume you have two algorithms A and B. A is O(n) and B is O(n^2). will the algorith for A always run faster than algorithm B? explain

Explanation / Answer

(a)f(n)=100 + 10log(base10)*(n)n^2 + 45n ==> O(n2log10(n) )

(b)nlog(base10)*(n) + nlog(base2) * (n)=> O(nlog2(n) ) -Because log 2n will generate bigger numbers than log 10

(c)Show the upper bound you give for f(n) above does indeed hold.

1.We can see that 100 + 10log(base10)*(n)n^2 + 45n <= 11n2log10(n)
there for f(n) <=cg(n)
2. We can see that nlog(base10)*(n) + nlog(base2) * (n) <= 2nlog2(n)
there for f(n) <=cg(n)


Thus we can say that it indeeds holds

(d)Assume you have two algorithms A and B. A is O(n) and B is O(n^2). will the algorith for A always run faster than algorithm B? explain
Yes , the algorith for A always run faster than algorithm B because the Time complexity depends on the Input size.

If Input n = 5 , The time takes by A (5) will be less than time taken by B

because B will take square of input size (25)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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