Consider the following nine functions for the questions that follow: 1. (n^2)/2
ID: 3815703 • Letter: C
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
Explanation / Answer
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)
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
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)