Question

Consider the following algorithm, which takes as input a sequence of ?n integers ?1,?2,…,??a1,a2,…,an and produces as output a matrix ?={???}M={mij} where ???mij is the minim term in the sequence of integers ??,??+1,…,??ai,ai+1,…,aj for ?≥?j≥i and ???=0mij=0 otherwise.

for i := 1 to n
  for j := 1+1 to n
    for k:= i+1 to j
      m[i][j] := min(m[i][j], a[k])
    end for
  end for
end for
return m

a.) Show that this algorithm uses ?(?3)O(n3) comparisons to compute the matrix M.

b.) Show that this algorithm uses Ω(?3)Ω(n3) comparisons to compute the matrix M. using this fact and part (a), conclude that the algorithms uses Θ(?3)Θ(n3) comparions. [Hint: Only consider the cases where ?≤?/4i≤n/4 and ?≥3?/4j≥3n/4 in the two outer loops in the algorithm.]

Answer 1

a.) The innermost assignment will take constant time to do the comparison and assignment.
The innermost loop (with k as the index) will run no more than n times. [The minimum possible
value to initialize k is i + 1, and the minimum possible value for i is 1 and the maximum value k
will ever go to is j and the maximum value that j will go to is n.]
The middle loop (with j as the index) will run no more than n times. [The minimum possible
value to initialize j is i + 1 which is 2. The maximum value j will go to is n]
The outermost loop (with i as the index) will run n times.
Therefore the runtime of the nested loops will take O(n) * O(n) * O(n) time
The initialization step of M will do one assignment for every element in M. M has n2 elements,
so this step will take O(n2) time.
Therefore the total runtime will be O(n3 + n2) = O(n3).

b.) First decide whether the function is big omega or not.

Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is Omega(g(x)) if there are constants C and k such that whenever f(x) >= C|g(x)|. [This is read as "f(x) is big-omega of g(x)="] One must note that in particular, f(x) is Omega(g(x)) if and only if g(x) is (f(x)).

The constants C and k in the definition of big-O notation are called witnesses to the relationship

The outer loop is executed at least n/4 times, once for each value of i from 1 to n/4. The middle loop is executed at least n/4 times, once for each value of j from 3n/4 to n. The inner loop for these values of i and j is executed at least (3n/4)- (n/4) n/2 times. Therefore the statement within the inner loop, which requires one comparison, is executed at least (n/4)(n/4)(n/2) = (n^3)/32 times.

Hence, the complexity of the algorithm is Omega(n^3).

From both the parts we can conclude that the complexity of the algorithm is .