Question

Consider the following nine functions for the questions that follow:

1. (n^2)/2 + 3

2. 3n^3

3. 2^n

4. 5n

5. 12n

6. 4^n

7. log_2(n)

8. log_3(n)

9. log_2(2n)

(a) Make a table in which each function is in a column dictated by its big-Θ growth rate. Functions with the same asymptotic growth rate should be in the same column. If functions in one column are little-o (o(n) = O(n) - Θ(n)) of another column, put the slower growing column on the left. If a column is little-ω (ω(n) = Ω(n) - Θ(n)) of another column, put the faster growing column on the right.

(b) If you multiplied every function by a factor of n, and fixed the table so that the functions were again sorted by growth rate, would that change the appearance of the table? If so, how? (If you aren’t sure whether something counts as a changed appearance, just describe what the new table looks like.)

(c) If you added n to every function in the table, would that change the appearance of the table? If so, how?

More info on little omega and little-o : https://www.slideshare.net/rkumardmh/little-o-and-little-omega

Show your steps to each answer

Answer 1

logarithmic	linear	quadratic	Cubic	exponential
log_2(n)	5n	(n^2)/2 + 3	3n^3	2^n
log_3(n)	12n			4^n
log_2(2n)

1. Part above

b)

logarithmic	linear	quadratic	Cubic	exponential
N* log_2(n)				2^n *n
N*  log_3(n)		5n *n	(n^2)/2 + 3	4^n *n
N*log_2(2n)		12n *n

3n^3 *n=3n^4 is polynomial of degree 4 we need 1 more colum for this

c log_2(n)+n=order of n because n is dominating factor

so similar for log3n and for log2(2n)

5n+n=5n

12n+n =12n

Because both are linear hence result is also linear

Quadratic ,exponenatial,cubic do not get affected by adding n hence they remain same

logarithmic	linear	quadratic	Cubic	exponential
	5n	(n^2)/2 + 3 +n	3n^3 +n	2^n +n
	12n			4^n   +n
	log_2(n)+n
	log_3(n)+n

                                           log_2(2n)+n