Course topic 3 exercises

Performance

Consider the pseudocode functions below. (It may help to recall insertion sort’s mechanism.) You can assume that only the things depicted affect the performance (efficiency) of the functions, so for example the performance of the APPEND()-function doesn’t matter.

  FunctionA(Array A):
    res := [[]] // empty 2D Array
    FOR i IN SIZE(A):
      FOR j IN SIZE(A):
        APPEND(res[i], A[i] * A[j])
      END LOOP
      APPEND(res, []) // Add empty array inside the 2D array
    END LOOP
    RETURN res

  FunctionB(Array A, Int target)
    FOR i IN A:
      FOR j IN A:
        IF i * j == target THEN
          RETURN [i, j]
        END IF
      END LOOP
    END LOOP

  FunctionC(Array A):
    IF SIZE(A) == 1 OR EMPTY(A) THEN
      RETURN TRUE
    ELSE IF FIRST(A) != LAST(A) THEN
      RETURN FALSE
    END IF
    POP_FIRST_AND_LAST(A) // Remove first and last elements
    FunctionC(A)

Question 1

Which functions won’t necessarily slow down at all even though the size of the input grows?

FunctionA

FunctionB

FunctionC

InsertionSort

Question 2

What can be said about the input for the best case for FunctionB?

All of the elements are equal in value

Elements are in descending order

First element of the array fulfills the requirement for the search

Question 3

And what can be said in the worst case for FunctionB?

All elements differ in value

All elements fulfill the search requirement

There’s no pair of elements that fulfills the requirement

The element’s are in randomized order

Question 4

For which function are the performances of the best case, worst case and average case all the same?

FunctionA

FunctionB

FunctionC

InsertionSort

Sum as a recursion

A+ presents the exercise submission form here.

Sum of digits as a recursion

A+ presents the exercise submission form here.

Posting submission...