0
$\begingroup$

Recently I have had this question in one of my interviews.

You have 1 Million sorted integer, you have a value of $x$, compare each pair in this array and if the addition of two pair is less or equal to $x$ then increment the paircounter.

I have implemented this solution in C++ however I will write pseudocode here(I am sorry I am not very good at pseudo-code)

Initialise ARR_SIZE to 1000000

Initialise index_i to 0

Initialise pairCount to 0

Initialise x to 54321

while index_i is less than ARR_SIZE

  Initialise index_j to index_i+1

    while index_j is less than ARR_SIZE

      if array[index_i]+array[index_j] is less or equal to x

        Increment pairCount

      increment index_j

    endof while

    increment index_x

endof while

At first I said it is $O(n \log n)$ but then with the hint the second loop itself average complexity is O(n/2) so overall I said it would be $O(n\cdot n/2)$ but in Big $O$ notation it would be $O(n)$ because $n/2$ is a constant(although I was not too sure). So what is the average complexity of this overall algorithm?

PS: I know that I could have decreased the complexity by adding an extra else, index_j = ARR_SIZE, which would be $O(N)$ complexity, but I couldn't think of it during the interview.

$\endgroup$
  • 1
    $\begingroup$ Your algorithm runs in $O(n^2)$. $n/2$ is not a constant ;) The problem in general should be solvable in $O(n)$. $\endgroup$ – Mike B. Jul 16 '13 at 14:53
  • $\begingroup$ Why O(n^2)? Let's say array size is 10, the first loop will run 10 times and second loop will run 5 times on average(as for total 10 times it would run 50 times). Again, I am asking the average case. The worst case would be 10 times 10 which is O(n^2) $\endgroup$ – Sarp Kaya Jul 16 '13 at 15:16
  • $\begingroup$ As @MikeB. said, $n/2$ is not a constant. Even in the average case you've defined, the complexity is $O(n^2)$. Remember, $O(n⋅n^2/2) = O(n^2)$. Try plotting a graph of iterations against $n$ (use $n = 0, 1, ... 100$ for example), where iterations equals $n⋅n/2$, you will see it's not linear. $\endgroup$ – Keir Simmons Apr 7 '14 at 7:21
2
$\begingroup$

How to solve it in O(N)

Let's take an example sequence of numbers:

1 3 4 6 7 9

Assume we want the number of pairs (A,B) where A + B <= 12.

First, let's compare the 1st (low element) and the Nth element (high element). 9 + 1 <= 12. So that's one pair. But, as our list is sorted, 9 is the biggest number, if (9, 1) <= 12, for any other number X in the list, (X, 1) <= 12! Meaning, we can just add 6-1 (high index - low index) to the count, we don't need to test those numbers separately. Those are pairs (9,1), (7,1) ... (3,1).

Now we increase our low index to 2, we continue to 3. 9 + 3 <= 12 still, so we add 6-2 to the count. We already added (3,1) in the previous step so this is fine. This adds pairs (9,3), (7,3), (6,3), (4,3).

Again we increase the low index. 9 + 4 > 12. When this happens, we decrease the high index and add nothing to the count.

Now low index is 3 and high index is N-1. 7 + 4 <= 12. Adding 5-3... And so on.

If it is unclear why I add high index - low index every time: take for example the 7 + 4 step. I know that, because I am at high = 7, I had to skip 9 because it was too large. So I don't want to add the pair involving 9. I also know that because I am at low = 4, I already counted the pairs involving 1 and 3 in the previous steps. So I need to add pairs (7,4) and (6,4) in this step.

int count = 0;
for (int low = 0, high = list.Count - 1; high >= 1 && low != high; )
{
    if (list[high] + list[low] <= x)
    {
        count += high - low;
        low++;
    }
    else
    {
        high--;
    }
}

Regarding constants and complexity

Judging by your comment, you are confused about what is ignored and why. First, n/2 is not a constant because it depends on n. As n grows, n/2 grows, so it is clearly not constant. The constant that is ignored in n*n/2 is 1/2, and what remains is n*n.

So the complexity is N^2. The actual number of inner loop executions is N^2/2, but this is still O(N^2). The fact you brought up in your comment that the inner loop will run 50 times when 10^2 would indicate 100 times is irrelevant, here's why:

Constants are not meaningful unless they are extremely large (a 2^32 constant because your algorithm tests every 32 bit integer) or you calculate the average case cycle count on a reference architecture.

Otherwise, actual speed depends on the language used, on how many instructions each operation actually performs, prediction, caching, pipelining, etc and it is difficult to compare the constants of 2 different algorithms, just outright counting syntactic constructs is very misguided.

2X operations may run faster than X operations if what is being done, how and in which order is different. So until you dig a bit deeper and look into the things I mentioned above, counting operations in a high level language is pure wishful thinking. It is a sign of a questionable CS teaching in my opinion because it teaches a nonsense model of code execution, instead of using a valid one, but on a simple reference architecture (like Knuth does), if you insist on counting operations.

Consider these two pieces of code:

for (int j = 0; j < N - 1; j++)
    for (int i = j + 1; i < N; i++)
        r += A[i][j];

And:

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

The first example has N^2 / 2 inner loop repetitions. The second example has N^2 inner loop repetitions. The inner loop body is the same. But the second one is actually much faster on a standard computer (in fact, a smart compiler with certain settings might rewrite your code if you write the first one - so if you test this, turn off optimization)! This is because the second one has much better memory access locality - it accesses the memory locations in order, while the first one jumps around. This causes a much bigger difference in speed than running the loop twice as many times does. And this is just one of many things which affect run speed and are not immediately visible in the code.

Second example, two pieces of code:

for (int i = 0; i < N - 1; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        int a = A[i][j] * 3;
        a += 5;
        r += a;
    }
}

And:

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

Can you tell me which one has a bigger "constant"? Again, the first inner loop runs 1/2 as many times as the second one. But the first one has 3 lines of code inside the inner loop, while the second one has just one. On my machine, the first one is faster. By what factor? I have no idea (I could measure it, but I can't tell you by looking at the code). If you decide on a constant A for the first and B for the second program by looking at the code, A/B will probably not be anything like the ratio of actual execution times, making the constants meaningless.

So the 1/2 constant is meaningless. Whether a program runs twice faster than some other program depends on so many things that it is not productive to account for small constants on such a superficial level.

By the way, you have a bug in your program. The outer loop condition needs to be less than ARR_SIZE - 1 or you are setting index_j to ARR_SIZE in the last outer iteration, and as your indices are 0-based you are reading from beyond the end of your buffer.

$\endgroup$
  • $\begingroup$ Thank you, also how can I do this in O(n) efficiency? $\endgroup$ – Sarp Kaya Jul 17 '13 at 4:55
  • $\begingroup$ "Constants are not meaningful unless they are extremely large" -- I don't know what element of the question causes you to go after constants, but I still want to note that even small constants matter. It is true, though, that constants change on their way from pseudo code to the processor. That is no excuse for sloppy algorithm design or analysis, though, but a prompt to test your hypothesis in a scientific fashion (cf Sedgewick). $\endgroup$ – Raphael Jul 17 '13 at 5:45
  • $\begingroup$ There is an "or ..." part of that sentence you cut off. If you analyse an algorithm properly, your constant can be meaningful, I covered that. But if you analyse them in a superficial way suggested by this question then no, they are not meaningful. By meaningful constant I mean you can claim the 2N algorithm is actually faster than the 5N one. If you can't claim that, then your "non-sloppy" analysis is in fact snake oil. If you can claim that, then it is fine. $\endgroup$ – svinja Jul 17 '13 at 8:05
  • $\begingroup$ For example, if you have a trivial case, such as 2 programs that are exactly the same except for the number of loop repetitions, then you can obtain a meaningful result by simply counting operations in a high level language. But in the general case it is not a useful approach (as in my examples). $\endgroup$ – svinja Jul 17 '13 at 8:14
  • $\begingroup$ @user1292095 I got so into my rant about constants I forgot to post the solution. I have now added it. $\endgroup$ – svinja Jul 17 '13 at 9:16
0
$\begingroup$

To add to @svinja's solution, instead of traversing the whole list of a million numbers, do the following -

L : List of million integers
S : @svinja's algorithm
Assuming indices start from 1 in L
int positionOfX = binarySearch(L, x), where positionOfX = -(insertionPoint) in case x does not exist in L

Apply S to L but traverse from 1 to i where i is at max abs(positionOfX/2) + 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.