Find the best running time for the following pieces of pseudocode. (a) Find the

Question

Find the best running time for the following pieces of pseudocode.

(a) Find the best running time for the following piece of pseudocode. s leftarrow 3 t leftarrow 1 i leftarrow 0 while 3^i lessthanorequalto 5 middot 3^n s leftarrow 1 s + 5t - 5i t leftarrow 5s - 1t + 5i i leftarrow i + 8 end while A. O(2^n) B. O(n) C. O(ln ln n) D. O(ln n) E. O(1) (b) Find the best running time for the following piece of pseudocode. s leftarrow 3 t leftarrow 1 i leftarrow 1 do s leftarrow 1s + 5t - 5i t leftarrow 5s - 1t + 5i i leftarrow 8i until 3^i > 5 middot 3^n A. O(Squareroot n) B. O(3^n/2) C. O(1) D. O(2^n/2) E. O(ln n)

Explanation / Answer

For Case 1 ) . We get 3(i+8)  = 5.3n

Taking Log both the side as solving we get ;

i log 3 + 8log 3 = nlog3 + log 5

=> i ~= N , Cancelling the constant parts

Approx we get O(N) , So B

For Case 3 ) . We get 3(8i)  = 5.3n

Taking Log both the side as solving we get ;

8I log 3 = n log3 + log 5
8I log 3 = n log3
8I = n

Again Taking Log both the sides we get

=> i ~= Log N , Cancelling the constant parts

Approx we get O(Log N) , So E is the answer

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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