If a program takes 20 microseconds to process a list of 10 numbers. How long would you expect it to take to process a list of 100 numbers? Answer the question in the different scenarios below, where T(n) represents the runtime as a function of n, the list size and k is a constant. Express the answer in appropriate units whenever it's bigger than 1000 microseconds (e.g. milliseconds, seconds, minutes, days, months, years)

. a)T(n) = k

b) T(n) = k (logn)

c) T(n) = k (sqrt(n))

d) T(n) = kn

e) T(n) = k *nlogn

f) T(n) = k (n^2)

g) T(n) = k (n^3)

h) T(n) = k(n^4)

i) T(n) = k (2n)

Show the steps.

Here are the notes about rule of thumbs.

T(n) k : T(n + r ) = k I f we increase the input size by any amount, the runtime is unchanged. Called "constant time"

T(n) klog(n) : T(n ² ) klog(n ² ) = 2klog(n) = 2T(n) If we square the input size, the runtime is doubled. Called "log time"

T(n) ksqrt(n) : T(4n) ksqrt(4n) = 2ksqrt(n) = 2T(n) If we quadruple the input size, the runtime is doubled . Called "sqrt time" See the general rule below when the scaling factor is something other than 4.

T(n) knlog(n) : T(2n) k(2n)log(2n) = 2kn(logn) + 2kn = 2T(n) + 2kn For large input sizes, If we double the input size, the runtime is slightly more than doubled. Called linearithmic or just "nlogn time."

More formally:

T(2n) / T(n) k(2n)log(2n) / (knlog(n)) = 2k (logn + 1) / logn = 2 + 2k/logn 2⁺ as n .

Also we have the relation T(n²) = kn² log(n²) = 2n kn log(n ) = 2n T(n). Meaning If we square the input size, the runtime is multiplied by twice the original input size.

One more: T(n ³) = kn ³log(n ³) which equal 3n ² knlog(n) = 3n ² T(n). So, If we cube the input size, the runtime is multiplied by three times the original input size squared.

More generally if we raise the input size n to power p, the runtime is multiplied by pn^(p-1).

T(n) = k(logn)² T(n ²) = k (log n ²) ² = k( 2 log n) ² = 4k(log n) ². = 4T(n). If we square the input size, the runtime is multiplied by 4.

And more generally for T(n) = k(logn) ^p, if we square the input size the runtime is multiplied by 2 ^p. If we cube the input size the runtime is multiplied by 3 ^p and so on..

T(n) kn : T(2n) k(2n) = 2kn = 2T(n) If we double the input size, the runtime is doubled. Called "linear time"

T(n) kn² T(2n) k(2n)² = 4kn² = 4T(n) If we double the input size, the runtime is quadrupled. Called "quadratic time"

T(3n) k(3n)² = 9kn² = 9T(n) If we triple the input size, the runtime is multiplied by nine.

T(rn) k(rn)² = (r²)kn² = (r²)T(n) If we multiply the input size by r, the runtime is multiplied by r squared.

T(n) kn(logn)² T(n²) = k(n²)(log(n²))² = 4nT(n) If we square the input size, the runtime is multiplied by four times the original input size.

T(n) = n²log (n). Then T(n ²) 2n ² T(n) and T(n ³) 3n ⁴T(n). Check this! Also think about generalizing to find rules for T(n) = n ^k log(n)

T(n) kn³ T(2n) k(2n)³ = 8kn³ = 8T(n) If we double the input size then the runtime is multiplied by eight. Called "cubic time"