COMP9024 (19T0)

COMP9024 (19T0) Sample Midterm Exam

Data Structures and Algorithms

Question 4 (4 marks)

The following algorithm

• takes a sorted array A[1..n] of characters
• and outputs, in reverse order, all 2-letter words νω such that ν≤ω.

  for all i=n down to 1 do
      for all j=n down to i do
          print "A[i]A[j]"
      end for
  end for

Answer the following questions:

1. Count the number of primitive operations (evaluating an expression, indexing into an array) for each line of the code.
2. What is the time complexity of this algorithm in big-Oh notation?

Type your answers to the above questions into the file called q4.txt and submit it using the command:

$ submit q4

The above command will make a copy of q4.txt as your answer for this question.