Please do all parts (a) Consider the procedure procedure Loopsl (n, a positive i
ID: 3816926 • Letter: P
Question
Please do all parts
(a) Consider the procedure procedure Loopsl (n, a positive integer) 1. for i = 1 to n 2. for j = i + 1 to n 3. print (i, j) i. In terms of n, how many ordered pairs are printed? ii. What is the runtime in theta notation of this procedure? (b) Consider the procedure procedure Loops2 (n, a positive integer) 1. for k = 1 to n 2. for i = 1 to n 3. for j = I + 1 to n 4. print (i, j) i. In terms of n, how many ordered pairs are printed? ii. What is the runtime in theta notation of this procedure? (c) Consider the procedure procedure Loops3(n, a power of 2) 1. for i = 1 to n 2. j = n 3. while j > 1 4. print (i, j) 5. j = j/2 i. In terms of n, how many ordered pairs are printed? ii. What is the runtime in theta notation of this procedure?Explanation / Answer
3. a)no. of pairs = n(n+1)/2
when n=2, pairs printed =1
when n=3, pairs printed =3
when n=4, pairs printyed =6 and so on , it can be seen in the sum of n natural nos. .
b) runtime is O(n^2-1)
outer loop runs n times, inner loop runs n-1 times so total runtime is n(n-1)=n^2-1
4. a) no. of pairs printed =n(n+1)^2/2
for n=3 , pairs printed = 9(3*3)
for n=4, pairs printed =24(4*6)
for n=5, pairs printed =50(10*5)
it can be seen that no. of pairs = n(n+1)/2 * (n+1) =n(n+1)^2/2
b) runtime notation = n*n*(n-1)=n^2(n-1)
5. a) no. of pairs printed = n*2^n
when n=2 , pairs printed = 1*2^1=2
when n=4 , pairs printed =2*2^2=8
when n=8, pairs printed =3*2^3=24
b) runtime notation =log n where n is the power of 2