Use probabilistic analysis of randomized algorithms to solve: For each of the fo

Question

Use probabilistic analysis of randomized algorithms to solve:

For each of the following problems, express your answer as theta (n^k) or theta (n^k (log n)) wherever possible. But if the asymptotic running time is exponential, then just give exponential lower bounds. Random (n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.) CoinFlip() returns heads or tails with equal probability. 1. Consider the following function: Func1 (A, n) /* A is an array of integers s leftarrow 0: for m leftarrow 1 to 10 do k leftarrow Random (n): for i leftarrow 1 to [n/k] do j leftarrow 1: while (j

Explanation / Answer

A. The asymptotic worst case running time of Func1 will be O(n2).

B . As the choices are random and the selected value is not fixed the asymptotic expected running time of Func1 will be (n log n).

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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