PLease answer as soon as possible 2. Write d down the worst case running time of

Question

PLease answer as soon as possible

2. Write d down the worst case running time of each of the function of n. Use the notation to partial credit. Sollowing code fragments as a Use the e notation to express your snswers. Show your work to receive (a) The arguments to this function are an element k anda list L of length n. function scan(k, list L) return i (b) The arguments to this function are two n × n matrices A and B. The function computes the matrix product A B and returns the resulting n x n matrix C. function matrixMult(A, B) for i 1 to n do for j i to n do return C

Explanation / Answer

2. (a) In worst case while loop will iterate n times i.e size of list
       therefore complexity will be "theta(n)"

   (b) Outer for loop will iterate n times
       Complexity: theta(n)

       now ,inner loop also iterate n times
       Complexity: theta(n)

       Hence over all complexity will be,
       theta(n) * theta(n)
       =theta(n^2)

   (c) Since each time function will search element k in half of its size
       Complexity will be theta(log n)

   (d) for each iteration of outer loop ,inner loop will execute n times
       therefore,for n iterations of outer loop inner loop will excecute n*n times.
       Hence complexity will be "theta(n^2)"

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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