Find all pairs (x, y) in a sorted array so that x + y < z

You cannot necessarily find all such pairs in O(n) time, because there might be O(n²) pairs of values that have this property. In general, an algorithm can't take any less time to run than the number of values that it produces.

Hope this helps!

In generate, no it can't. Consider the case where x + y < z for all x, y in the array. You have to touch (e.g. display) all of the n(n - 1)/2 possible pairs in the set. This is fundamentally O(n^2).

If you are asked to output all pairs that satisfy that property, I don't think there is anything better than O(N^2) since there can be O(N^2) pairs in the output.

But this is also true for x + y = z, for which you claim there is a O(N) solution - so I might be missing something.

I suspect the original question asked for the number of pairs. In that case, it can be done in O(N log(N)). For each element x find out y = z - x and do a binary search for y in the array. The position of y gives the number of pairs that can be formed with that particular value of x. Summing this over all values in the array gives you the answer. There are N values and finding the number if pairs for each takes O(log(N)) (binary search), so the whole thing is O(N log(N)).