Algorithm Analysis Problems #4) Please explain the solution thoroughly it\'s mor

Question

Algorithm Analysis Problems #4)

Please explain the solution thoroughly it's more important than the answer itself. Here is my class work and a provided link to origonal word document. Thank You.

https://docs.google.com/document/d/1sgmQ24EZxDZL7WfqPh_hjz2MNu2wGGvl47rQrmFeagY/edit?usp=sharing

4. (10 pts) Consider the following algorithm. Assume n is a power of 2 oyn while i do I Keep tending You aet A while j n do laa n e(1) statements endwhile end while A Vogn What is the complexity of the algorithm? Circle one of the following answers: Sub natation

Explanation / Answer

Ans: iii

Here, There are two while loops:
   One in inner and other is outer

   In Outer while loop:
       It iterates log(n) time because in each iteration we are dividing n by 2

       So, we know, n + n/2 + n/4 + .... = O(logn)

   In Innner while loop:

       for each value of i, loop is iterating log(n) times, because in each iteration we are multiplying j by 2

       so, 1 + 2 + 4 + 8 + .. n terms = log(n)

So, time complexity : O(logn)*O(logn) = O((logn)^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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