Page 3 Question 8 0: Consider the following pseudocode: Algorithm roundRobinTour
ID: 3856078 • Letter: P
Question
Page 3 Question 8 0: Consider the following pseudocode: Algorithm roundRobinTournament (a) This algorithm generates the list of matches that must be played in a round - robin pirate - dueling tournament (a tournament where each pirate duels each other pirate exactly once) a is an array of strings containing names of entrants into a tournament n a.length for i = 0 to n-1 for j i+1 to n-1 print a[i]duels "al] ", Yarrr!" (a) (5 points) Determine the exact number of statements (i.e. use the statement counting approach that are executed by the above algorithm. Express your answer as a function of n. Show all your calculations (b) (1 point) Express the function you obtained in part a) in big-O notationExplanation / Answer
Question 8:
a)
n is the length of the array, that starts from 0.
i is starting from 0 to n-1. So the loop will iterate n times.
j is starting from i+1 to n-1.
Lets say n-1 as k
I 0 1 2 3 4 . k-1 k
J 1 2 3 4 5 . k .
1 to k 2tok 3tok 4tok 5tok . ktok .
k-1 times k-2 times k-3 times k-4 times k-5 times 0 .
Therefor the function as n is, n(n-1)/2.
The statements will execute these many times.
b)
=n(n-1)/2
= (n2-n)/2
= O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.