Algorithm roundRobinTournament(a) This algorithm generates the list of matches t

Question

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 an tournament

n = a.length
for i = 0 to n-1

for j = i+1 to n-1
print a[i] + "duels" + a[j] + ",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- notation.

Explanation / Answer

n = a.length                                                   1
for i = 0 to n-1                                               n/2(n-1)
for j = i+1 to n-1                                               n/2(n-1)
print a[i] + "duels" + a[j] + ",Yarrr!"                       n/2(n-1)

this is calculated as follws:

it is as follows:

1
i=0
n
n
i=1
n-1
n-1
.
.
.
i=n-1
0

total= n(n-1)+ n/2(n-1)+1

big- notation= O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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