0

I recently solved the Merge Sorted Array question on leetcode
Here is the part of the code I am having doubts on :

while (curr >= 0 && p1 >= 0 && p2 >= 0) {
    // more TC if we use the condition >= , not sure of the reason 
    if (nums1[p1] > nums2[p2]) {
        nums1[curr] = nums1[p1];
        nums1[p1] = 0;   // replacing 0 and greater number in nums1
        p1--;
    } else {
        nums1[curr] = nums2[p2];
        p2--;
    }
    curr--;
}

I noticed that when I use >= in the while condition (instead of >), the time complexity seems to increase or the solution behaves slower. Why ?

Improve this question
6
  • 4
    Which one of the three (four) >= are you talking about? Please update your answer. Commented Nov 21 at 17:10
  • Naturally if you use >= instead of > you'd have 1 extra case in all scenarios to compute for: the == case. So you've already got inherently more work out the gate, computational performance aside. Commented Nov 21 at 17:22
  • 3
    Time or Time Complexity? It does not increase Time Complexity, which is a rough estimate method of comparing best/worst/average cases. It's still O(whatever). It might increase time to run the algorithm, depending on the exact data fed, but not the complexity. Commented Nov 21 at 17:42
  • 3
    @GabeSechan - " ... Time Complexity, which is a rough estimate method of comparing best/worst/average cases ..." is inaccurate. 1) The 'case' (best/average/worst) that you are measuring is orthogonal to the method of measurement (complexity). 2) Complexity is actually a characterization of how the algorithm scales rather than a "rough estimate". For a start, complexity doesn't give you a meaningful number. Commented Nov 22 at 10:34
  • Time complexity seems to be a red herring here. In particular, you clearly have not performed either an algorithmic analysis to show higher complexity, nor comparative performance measurements to distinguish higher complexity from (mere) longer runtime. It follows that although the question is about an observed performance difference, attributing that difference to different time complexity is wholly speculative. Commented Nov 23 at 15:03

2 Answers 2

Reset to default
2

solution becomes slower

If none of the elements in nums1 are equal to elements in nums2, the solution won't become slower by using >=. If some or all of the elements in nums1 are equal to elements in nums2 they won't get moved if using >, but will get moved and increase number of compares if using >=, making the solution slower.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Your variables m and n appear to be the numbers of elements in the two partitions being merged. Sure, you can compute the time complexity of the merge in terms of these parameters, but the difference there between O(n) and O(m+n) doesn't speak to the complexity of the overall sort, which is what the question seems to be asking about.
Nothing I said is inconsistent with any of that. Again, the difference there between O(n) and O(m+n) doesn't speak to the complexity of the overall sort. To clarify, that's because, as such a merge is used in a merge sort, these parameters are correlated with each other, and correlated with, but not necessarily equal to, the appropriate dimension parameter for the sort overall.
Also, however, although you can compare the functions n and m+n for different values of their parameters, you cannot compare O(n) to O(n+m) on the same basis. O() is a second-order function, not a function of the parameters of its operand functions.
I updated my answer, removed comments about time complexity, only responding to "making solution slower".
0

Assuming you mean the inner > with >=- there can be several answers. One obvious one is that the if branch does more work, so putting more in there is slower. I'm not sure why you have nums1[p1] = 0; in there, it doesn't seem necessary. Beyond that you can get into things on the hardware and interpreter level- the JIT cache guessing wrong on the branch prediction (or the hardware itself). Locality issues in the cache maybe. But its mostly going to be the extra instruction most likely.

If you mean one or more of the > in the while loop- yeah, that adds more cases where the while loop runs. More runs=more time.

Although as I stated in a comment- this is time to run, not time complexity. None of these would change time complexity.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.