Suppose L is of type List, whereas p, q, and r are of type position. Consider th

Question

Suppose L is of type List, whereas p, q, and r are of type position. Consider the following algorithm. p: = First (L); while p EndPos(L) do begin q: =p; while q End Pos(L) do begin q: = Next (q, L); r: = First(L); while r q do r: = Next(r, L) end; p = Next (p, L) end; Assume that the length of list L is n. As a function of n, determine how many times the functions First, EndPos, and Next are executed by the above algorithm Rewrite the code for the List operations assuming a linked list representation However, there is no header cell (i.e. dummy cell). Assume true pointers are used and position l is represented by nil.

Explanation / Answer

4)

Assuming,

First(L) returns first position of List L.
EndPos(L) returns last position of List L.
Next(q,L) returns the next element after q in list L.

and length of the list is 'n'.

First() - once on the 1st line
       + within the loop.
      
   Here outer while loop will run n times and for every iteration of outer loop, inner loop will run n times.
   Totally the First() will run n*n times.
      
   In total, the First() will run = n2 + 1 times.
  
  
EndPos() - For every check in the outer loop + for every check in inner loop.
       = Outer loop will run n times and for every iteration of outer loop, inner loop will run n times.
       = n*n times.

Next()    -   once in the outer loop + once in the inner loop + again in the innermost loop.

       (For innermost loop, in worst case, it will again loop for the entire length of the list.)
      
       = n + (n*n) + (n*n*n) times.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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