Program and run time determination

Question

Given the following pseudo code

D(A) // A is an array of numbers
U_Size = 1
for i=2 to length(A)
   U=?
   for j=1 to U_Size
      if A[j]=A[i]
        then U = FALSE
            j = U_size
   if U = TRUE
     then U_Size = U_Size + 1
        A[U_Size]=A[i]
return U_Size
 

1. What will be the best opton to replace the "?" in line 4? ( U=? )
   and what exactly does this program do - Answered
2. How should I determine the run-time & space complexity of this program

MY ANSWER: In line 4, I initialized U -> U = TRUE and figured that the program arranges all of the different elements of the array in the beginning of the arry and returns the amount of different elements
The Question remained unanswered is: How should I determine the run-time & space complexity of this program (2)

Answer 1

If you are not familiar with the Big O notation, I would suggest to read about it because in computer science we use that to represent the time and space complexity.

Let the length of input array is n.
The time complexity of this code will be O(n²) in the worst-case and the worst-case occurs for an array of all distinct numbers. For an input array of all distinct numbers, the if condition if A[j] = A[i] is always false, so the inner looop of j loops from 1 to U_size for every i and U_size is increased by 1 everytime.
If it is still not clear then you can understand it using math for an array of all distinct numbers.

For i = 2, and U_size = 1, the inner loop of j runs from 1 to 1 i.e 1 time.
For i = 3, and U_size = 2, the inner loop of j runs from 1 to 2 i.e 2 times.
For i = 4, and U_size = 3, the inner loop of j runs from 1 to 3 i.e 3 times.
For i = 5, and U_size = 4, the inner loop of j runs from 1 to 4 i.e 4 times.
.
.
.
.
.
For i = n (length of array A), and U_size = n-1, the inner loop of j runs from 1 to n-1 i.e n-1 times.

So, if you sum up the running times for all the iterations of i,
1 + 2 + 3 + 4 + ... + n-1, you get n*(n-1)/2 which is ~ O(n²).

---

Now, space complexity. You have used the array A itself for assigning after the j loop. If you do not take into account the input array for reporting space, then you get O(1) as space complexity.

If you store a separate array for assigning the element i.e A[U_Size]=A[i] or you consider the input array itself for space, then you would say space complexity as O(n).