3. (a) Consider the procedure procedure Loopsl (n, a positive integer) 1, for i

Question

3. (a) Consider the procedure procedure Loopsl (n, a positive integer) 1, for i 1 to n for j = i to n print (i,j) i. In terms of n, how many ordered pairs are printed? ii. What is the runtime in notation of this procedure? (b) Consider the procedure procedure Loops2 (n, a positive integer) I. for k = 1 to n-2 for i=k+1 to n-1 for j=i+ 1 to n print (i,j) i. In terms of n, how many ordered pairs are printed? ii. what is the runtime in notation of this procedure? (c) Consider the procedure procedure Loops3(n, a power of 2) 1, for i 1 to n =n while j >1 print (i,j) i. In terms of n, how many ordered pairs are printed? ii. What is the runtime in notation of this procedure?

Explanation / Answer

ANSWER :

(a) procedure Loops1(n, a positive integer)
for i = 1, j will execute print for n times, for i = 2 j will execute print for n-1 times and so on
(i)here pairs will be printed for n + (n-1) + (n-2) + ...+ 3 + 2 + 1
= n(n+1)/2

(ii)here first loop will be be executed for n+1 times and second loop will be executed for n(n+1) times

Now, T(n) = (n+1) + n(n+1)
= n+1+n^2+n
= n^2 + 2n + 1
T(n) = (n^2)

(b) (i)here pairs will be printed for n(n((n-1)+(n-2)+....+2+1)
= n(n(n-1)/2)
(ii) Here no of times the loop will be executed
T(n) = (n+1) + n(n+1) + n(n(n+1))
= n+1+n^2+1+n^3+n^2
= n^3+2n^2+2n+1
T(n) = (n^3)

(c) here n = 2,4,6,8,....
for n = 2
print will be executed for 1 time
for n = 4
print will be executed for 2 time
and so on.
(i) here pairs will be printed for nlog2(n)
(ii) T(n) = (nlog(n))

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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