Question

function max-diff(array a[1..n])
m := 0

for i := 1 to n-1

for j := i + 1 to n

if |a[i] – a[j]| > m then

m := |a[i] – a[j]|
end-if
next
next

end proc


What's the O(Upper bound) and θ(lower bound) time complexity of this algorithm.

Answer 1

Answer:

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}

Output: 6 (j = 7, i = 1)

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}

Output: 5 (j = 5, i = 0)

Input: {6, 5, 4, 3, 2, 1}

Output: -1