What will be the complexity of this code? Should we sum complexities?

Question

I have an algorithm which ,at first, sorts the vector and then iterate through its elements and XOR them. Should I sum the complexities of sort and for loop to calculate the overall algorithm complexity? So, I have next code:

std::sort(array.begin(), array.end());
for (int i =1; i < array.size(); ++i) {
  result = array[i-1]^array[i];
}

We have a for loop which has O(N) complexity and std::sort which has O(N log N) comparisons on the average. So the complexity of the next code will be O(N + N log N)? Or in this case we just have to choose the highest time complexity class which is linearithmic time O(N log N) and don't sum them?

***for (int i =1; i <= array.size(); ++i) {*** You have UB when you access `array[i]` in the next line when i = array.size(). — drescherjm, Jul 03 '16 at 16:44
`array[array.size()]` is out of bounds. look when i== array.size(). result = array[array.size()-1]^array[array.size()] — drescherjm, Jul 03 '16 at 16:48
@Arunmu Because complexities don't sum? We just select the highest? — MainstreamDeveloper00, Jul 03 '16 at 16:48
@MainstreamDeveloper00 EricDuminil has summed it up pretty well. And we do that because with 'O' we are looking for an _upper_ bound. — Arunmu, Jul 03 '16 at 17:48

score 1 · Accepted Answer · edited Apr 13 '17 at 12:19

1

The runtime is bounded by the sorting step, O(nlgn). The for loop may have O(n) complexity, but the overall runtime is always dominated by the highest power. See here for a mathematical proof:

https://math.stackexchange.com/questions/324200/big-o-notation-sum-rule

edited Apr 13 '17 at 12:19

Community

1
1

answered Jul 03 '16 at 16:53

ifma

3,673
4
26
38

score 1 · Answer 2 · answered Jul 03 '16 at 16:54

Yes, you can sum them: O(n) and O(n log n) becomes O(n + n log n). But note this is not O(2n log n) as you suggest, because addition comes after multiplication in basic arithmetic.

Now, just as O(1 + n) is always reduced to O(n), your O(n + n log n) will be reduced to O(n log n) because the solitary n term is less than the n log n term, and big-O notation is always about the limits, not the exact equation.

Some people might find it more intuitive to recognize from the outset that O(n) is dominated by O(n log n), and never sum them in the first place. That's a useful mental shortcut, but both perspectives get you the same result.

score 0 · Answer 3 · answered Jul 03 '16 at 16:49

0

The complexity class O(N) is a subset of the class O(N log N), since log N > 1 for sufficiently high N. Thus, the complexity class of the code O(N + N log N) is a subset of O(2 N log N), and since the complexity classes are invariant w.r.t. constants, it's O(N log N) at the end.

answered Jul 03 '16 at 16:49

theV0ID

4,172
9
35
56

Why the down-vote? Explain. – theV0ID Jul 03 '16 at 16:52

score 0 · Answer 4 · answered Jul 03 '16 at 16:53

The way we calculate complexities is by choosing the highest among all the ones.

So, lets suppose you have the following code

for i in range 0 to n
{
    for  in range 0 to n
    {
        \\ code
    }
}

for i in range 0 to n
{
    \\ code
}

So, here there the complexities would be O(n^2) + O(n). Which would finally be O(n^2). So, the complexity of the whole above code is O(n^2).

Similarly, in your case the complexity is O(N log N) + O(N), which makes the final complexity to be O(N log N)

score 0 · Answer 5 · answered Jul 03 '16 at 16:57

0

First of all, O(N+N log N) would not give you O(2N log N), it would give you O( (log N+1) * N). This algorithm would be bounded by O(N log N), as this grows faster than O(N) as N approaches infinity.

answered Jul 03 '16 at 16:57

Ethan Yang

48
4

What will be the complexity of this code? Should we sum complexities?

5 Answers5