Question

I didn't answer for the prevuise question

1. A program takes time proportional to the log of the input size. If the program takes 100ms for input size 1,000, how many milliseconds does it take for input size 1,000,000?

2. A program takes time proportional to the square root of the input size. If the program takes 100 ms for input size 500, how many milliseconds does it take for input size 2,000?

3. A program takes time proportional to the cube of the input size. The first run, with a given input size s, takes 10 ms. The second run is with input size 3s.  How many milliseconds does the program take this time?  (Type in just the number; don't type "ms" at the end.)  

4. Suppose the runtime of a compute program is proportional to n⁴ where n is the input size. If the original runtime is 11 for input size 1000, what is the new runtime for input size 3000?

5. Supppose program takes time proportional to n² where n is the input size. If the program takes 2 milliseconds for input size 10, how many milliseconds does it take for input size 20 ?

Answer 1

1. A program takes time proportional to the log of the input size i.e. T(n) = Order (log(n))

given T(n) = 100 ms for 1000 i.e    100 = O(log(1000))

for 1,000,000 which is 1000² we get   T(n) = O(log(1000²)) =O(2* log(1000)) =2* O(log(1000)) =200

2. A program takes time proportional to the square root of the input size. i.e. T(n) = Order( n^0.5 )

given for O((500)^0.5) output = 100 , for 2000 =500*4 we get output = O((500 *4)^0.5) =2* O((500)^0.5) =2 * 100 =200

3. A program takes time proportional to the cube of the input size T(n) =Order(n³)

given for s output is 10   so for 3s we get O(n³) =O((3s)³) = O(9s³)= 9*10 =90

4. the runtime of a compute program is proportional to n⁴ where n is the input size

for input 1000 output is 11 ie O(1000⁴) = 11

for O(3000⁴) we get 3⁴ *O(1000⁴) =81*11 =891

5. program takes time proportional to n² where n is the input size

for input 10 output is 2 applying similar procedure output for 20 = 2²* O(10²) = 4*2 = 8