Growth Functions by speed(Big Oh Notation) (Computer Science) Consider the follo

Question

Growth Functions by speed(Big Oh Notation) (Computer Science)

Consider the following functions f(n) and answer the following questions.
exponential: 2n
quadratic polynomial: n2
logarithmic: log(n)
cubic polynomial: n3
n log n: n log(n)
factorial: n!
linear: n

Question 1) Which of these functions grows the fastest?
Question 2) Which of these functions grows the slowest?
Question 3) Order these functions from #1 fastest growing to #7 slowest growing.

1.
2.
3.
4.
5.
6.
7.

Question 4) If these functions f(n) represent algorithm run times as a function of problem size n,
which of the functions has the slowest run time?

Question 5) If these functions f(n) represent algorithm run times as a function of problem size n,
which of the functions has the fastest theoretical run time?

Explanation / Answer

Q1.) factorial grows the fastest as for each iteration, the number of operations performed in the nth iteration is 2n.

Q2.) linear n grows the slowest as Constant algorithm does not depend on the input size.

Q3.)1.factorial

2.exponential

3.cubic

4.quadratic

5.nlogn

6.nlog

7.n

Q4.)factorial has the highest run time as for each iteration, the number of operations performed in the nth iteration is 2n.

Q5.) linear n has the fastest run time as Constant algorithm does not depend on the input size.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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