- 12 Marks Dodging The Target Consider A Problem We Will Call The No Pairs Sum Problem Given An Array A Storing N Inte 1 (57.67 KiB) Viewed 45 times
worst-case analysis to compute the time complexity of the below
algorithm. You must give the order of your complexity function
using Big-Oh notation, and you must explain how you computed the
time complexity. Without Hashmap.
function NoPairSum(Array, target) {
for i=0 to len(Array)-1 {
for j=i+1 to len(Array)-1 {
if (target ==
Array+Array[j])
return
false
}
}
return true
}
[12 marks] Dodging the Target. Consider a problem we will call the no-pairs sum problem: Given an array A storing n integers and an integer t called the target as input, determine whether it is the case or not that no pair of elements in A that, when added together, sum to the target t. That is, if there exists two elements at indices i and j for array A where A + A[j] = t, return false; return true if every pair of elements in A fail to sum to t. Below are four example problem instances, where its solution is provided below the input instance. 1 t = 6 0 1 2 3 4 5 6 1381 2 3 4 false 0 1 2 3 4 5 4 1 2 2 68 false 0 1 2 3 11827 true 0 1 2 3 4 t = 20 10 9 8 6 4 5 6 7 32 1 t=8 true