Question

Use pseudocode to describe an algorithm that displays the last occurrence of each element in an input sequence a_0,a_1,…,a_n. In other words, if an element appears more than once in the sequence, only the last occurrence is displayed.

Example:

4, -5, 3, 2, 3, -1, 4, 3  displays -5, 2, -1, 4, 3

Determine the running time of your algorithm as a function of n (in the worst, best and average case) and then use asymptotic notation to simplify it.

Answer 1

Answer on Question#71969 – Math | Discrete Mathematics

Use pseudocode to describe an algorithm that displays the last occurrence of each element in an input sequence $a_0, a_1, \ldots, a_n$. In other words, if an element appears more than once in the sequence, only the last occurrence is displayed.

Example:

4, -5, 3, 2, 3, -1, 4, 3 $\diamond$ displays -5, 2, -1, 4, 3

Determine the running time of your algorithm as a function of $n$ (in the worst, best and average case) and then use asymptotic notation to simplify it.

Answer

Declare array array1
Declare array array2
For index = 0 to Length(array1) - 1
    Input array1[index]
End For
For index = 0 to Length(array1) - 1
    Set array2[index] = 1
End For
For index1 = 0 to Length(array1) - 2 //so, the array length is 3 minimum
    Set w = 0
    For index2 = index1 + 1 to Length(array1)
        If array1[index1] == array1[index2] then
            Set array2[index1] = 0
        End For
    End For
For index = 0 to Length(array1) - 1
    If array2[index] == 1 then
        Display array1[index1]
    End For

Running time of the algorithm on the $n$-length array is $n + n + (1 + 2 + \ldots + n) + n = 3n + (1 + n)^n / 2$.

Simplifying it using asymptotic notation: $3n + (1 + n)^n / 2 \rightarrow (1 + n)^n / 2 \rightarrow (1 + n)^n \rightarrow n^*n$ in every case.

Answer provided by www.AssignmentExpert.com