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.

PLEASE EXPLAIN IT

Explanation / Answer

Algorithm roundRobinTournament(a)

n = a.length-----------> Runs 1 time

for i = 0 to n-1------> runs n+1 times ( +1 because of one failure condition)

for j = i+1 to n-1-->------> runs n [ (n-1)/2 + 1 ] times ( when i=0, runs n times , i=1 runs n-1 times , i=n-1 runs 2 times )

print a[i] + "duels" + a[j] + ",Yarrr!----->Runs n*[2+3+4+..............n] = n [ (n-1)/2 ]

b) If we sum up everything, we get
n [ (n-1)/2 ] + n [ (n-1)/2 + 1] + n+1 +1 => =>(n2)


Thanks, let me know if there is any concern

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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