HELP!!! HELP!!! HELP!!! 1)Suppose we have an algorithm whose processing time T(N

Question

HELP!!! HELP!!! HELP!!!

1)Suppose we have an algorithm whose processing time T(N) for an array of size N has a relation with T(N – 1) such that T(N) = 0.5*T(N-1) + 10. Solve the recurrence relation to reach a closed form solution for T(N).

2)An algorithm with time complexity O(f(N)) and processing time T(N) = cf(N), where f(N) is a known function of n, spends 10 seconds to process 1000 data items. How much time will be spent to process 1000,000 data items if      1) f(N) = logN;         2) f(N) = N;               3) f(N) = N3;                 4) f(N) = 2N.

3) An algorithm with time complexity O(f(N)) and processing time T(N) = cf(N), where f(N) is a known function of n, spends 10 seconds to process 1000 data items. How much time will be spent to process 1000,000 data items if      1) f(N) = logN; 2) f(N) = N; 3) f(N) = N3;         4) f(N) = 2N.

Explanation / Answer

The constant factor c = T (1000) 10000 ms and f(1000) milliseconds per item.

There- f(1000) ms and T(100, 000) = 10 f(100,000) fore, T(n) = 10 f(n) f(1000) = 10 f(1000) ms.

If f(n) = n then T(100,000) = 1000 ms.

if f(n)=log. then=2000 ms

If f(n) = n3, then T(100, 000) = (10)7 ms.

if f(n)=2n,then 2000ms

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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