Algorithm performance Give the order of magnitude Theta () for the following alg

Question

Algorithm performance Give the order of magnitude Theta () for the following algorithm. Explain why your answer is correct. GET VALUES for A_1, A_2, .. ., A_n, and B_1, B_2, .. ., B_n Get value of n i = 1/* set i equal to 1 */DO WHILE (i lessthanorequalto n)/* for each of the n values in A */j = 1/* set j equal to 1 */DO WHILE (j lessthanorequalto n)/* Do n times *1 IF Ai = Bj THEN PRINT "Found it!" j = j + 1/* increment j */END DO WHILE i = i + 1/* increment i */END DO WHILE Explain what the algorithm does.

Explanation / Answer

For each value of A, it is searching in B. So basically this algorithm finding the comman elements.

Here we have two do while loop. One is nested in other.

Since size of A and B is n.

So, T(n) = 1 + 2+ 3+ ...+n = n(n+1)/2 = O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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