express your answer as (nk ) or (nk (log n )) wherever possible. But if the asym

Question

express your answer as (nk ) or (nk (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.

Func1 (A, n) A is an array of integers 2for m 1 to 10 do k Random(n): for i 1 to L do while(j n) do 6 7 8 9 ss+A[i] * A[j]; end 10end 11 end 12 return (s (a) What is the asymptotic worst case running time of Func1? (b) What is the asymptotic expected running time of Func1?

Explanation / Answer

Let me first explain the normal running time complexity.. that is asked in part 2.

So the Line number 2 has a loop of m, which varies from 1 to 10. It means Loop at line 2 will work for 10 times.

Line 3 gets a random value of k which is in range of [1, n], Now based on this value the total range of n is divided into k parts and hence line number 4 is executed (n/k) times.

Line 5 starts with j=1 and tries to double the value of j in each iteration of loop at line 6, till the time value of j doesn't become equal to or greater than n.. This step takes log(n) time.

So the overall complexity can be found by multiplying each of these steps: 10 * (n/k) * log(n)
As 10 is a constant factor, we can neglect that.. hence the overall expected complexity is (n/k) * log(n)

now the worst case will happen when k = 1, at that time, we will get the loop at line 4 to be running for n number of times exactly and thus the overall complexity will become n*log(n).

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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