Find a growth rate that squares the run time when we double the input size. That

Question

Find a growth rate that squares the run time when we double the input size. That is, if T(n) = X, then T(2n) = x^2 Find a growth rate that cubes the run time when we double the input size. That is, if T(n) = X, then T(2n) = x^3 Using the definition of big-Oh, show that 1 is in O(1) and that 1 is in O(n). Using the definition of big-Oh and ohm find the upper and lower bounds for the following expressions. Be sure to state appropriate values for c and n_0. c_1 (n) c_2 n^3 + c_3 c_4 n log n + c_5 n c_6 2^n + c_7 n^6

Explanation / Answer

Clearly, it satisfies for exponential growth rates, i.e., n is in the exponent of some constant.

3.6 Part A
----------------------------------------

Let's say T(n) = e^n
So, if n' = 2n,
then T(n') = e^n' = e^2n = (e^n)^2 = ( T(n) )^2
Hence, T(n) = e^n squares if the input size(n) is doubled

3.6 Part B
-------------------------------

Let's say T(n) = e^(3n/2)
So, if n' = 2n,
then T(n') = e^(3n'/2) = e^(3n) = (e^(3n/2))^3 = ( T(n) )^3
Hence, T(n) = e^(3n/2) cubes if the input size(n) is doubled

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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