0

So guys, I've already asked a question about how to develop an algorithm here.

The reviewed code looks like this: (note that I've put the elements in the vector L all equal in order to maximize the iterations of the program)

L = [2 2 2 2 2 2 2 2 2];
N = 3;
sumToN = [0 0];
Ret = [0 0];
k = 0;

for i=1:numel(L)-1;
  for j=i+1:numel(L);
      if L(i)+L(j) == N
     sumToN = [L(i) L(j)];
     display(sumToN);
     return
      end
      k=k+1
  end
end
display(sumToN);

The k variable is used to keep count of the iterations. The function that counts the number of steps of the algorithm is (1/2)(x-1)x, with x being equal to the number of elements in the vector L. The problem is that the exercise asks me to ensure that the algorithm completes in at most c*numel(L) for some positive constant c that does not depend on L. Moreover, I need to explain why this implementation completes in at most c*length steps.

How can I do it?

Community
  • 1
  • 1
james42
  • 307
  • 5
  • 16
  • Your code does not completes in at most `c * numel(L)`, it completes in at most `numel(L) * numel(L)` which is very different. – Holt Jul 31 '15 at 09:32
  • I know, but how can I make the algorithm complete that way? – james42 Jul 31 '15 at 09:42

2 Answers2

0

There is a contradiction in your statements: You say that your algorithm complete in x * (x - 1) / 2 (x = numel(L)), and you want to prove that your algorithm completes in c * x (where c is a constant). This is not possible!

Let's assume there is c1 such as x * (x - 1) / 2 <= c1 * x, it means that x must be less than 2 * c1 + 1, so if I take x = 3 * c1, the inequation is not true anymore, so there is no c such as x * (x - 1) / 2 <= c * x for all x.

Here is an algorithm that works in O(x) with a sorted array (from your previous question):

i = 1
j = length (L)
while i < j
    if L(i) + L(j) == N
        sumToN = [L(i) L(j)];
        break
    elseif L(i) + L(j) <  N
        i = i + 1;
    elseif L(i) + L(j) >  N
        j = j - 1;
    end
end

Basically, you start with the first (smallest) value and the last (larger) value, and you move towards the middle of the array L as long as your two indexes do not cross.

Holt
  • 36,600
  • 7
  • 92
  • 139
0

Another way i think you could only have a single for, to get that condition you're talking about, would be to process a bit like this :

  • for each value of L, check if there is the value (L-N) in your list L (use a command to find a value in your list, that would return the position in the list)
  • If the value exist, put that pair of position in your new table.

You should be able to get the same result with a single for.

Peut22
  • 304
  • 1
  • 11
  • This is just a cover for the second `for` loop because the find as a `O(n)` complexity, so the global complexity would still be `O(n ** 2)` (the second `for` is hidden inside the `find` function). Knowing that the array is sorted, the complexity of `find` drops to `O(log(n))` but the global complexity would still be `O(n * log(n)) > c * n` for `n` large enough. – Holt Jul 31 '15 at 09:58
  • Indeed, as i finished, i saw your edid with a sorted array, which makes sense to reduce notably the complexity. But i don't really see a way to match the acceptance criteria of the question though. – Peut22 Jul 31 '15 at 10:02
  • 1
    If you follow the link provided by the OP, you'll see that the original question uses a sorted array. A `O(n)` algorithm is possible on a non-sorted array if you have access to a hashmap with a `O(1)` hash complexity: First you create a hashmap where the key are the value of the array and the value are the key, then for each value `a` in the array, you check if the key `N - a` is in the hashmap (assumed also `O(1)` for hashmap). – Holt Jul 31 '15 at 11:24