0

I recently saw this simple 'two number sum' code in some website. While abalysing the time complexity, it was mentioned that the time complexity of the following code in O(N). I'm wondering if it is O(Nlog(N)) as the 'for' loop involves O(N) and the C++ STL method "find()" is used inside this loop, which may have a time complexity of O(log(N)). So I'm wondering if the overall complexity should be O(Nlog(N)) instead of O(N).

Apologies if this topic is already discussed before, but I couldn't find when I searched. I appreciate a good explanation if the time complexity is indeed O(N).

#include <bits/stdc++.h>

using namespace std;

void printPairs(int arr[], int arr_size, int sum)
{
    unordered_set<int> s;
    for (int i = 0; i < arr_size; i++)
    {
        int temp = sum - arr[i];

        if (s.find(temp) != s.end())
            cout << "Pair with given sum "
                 << sum << " is (" << arr[i] << ","
                    << temp << ")" << endl;

        s.insert(arr[i]);
    }
}
Vicky
  • 1
  • happy reading here https://stackoverflow.com/questions/962545/on-log-n-complexity-similar-to-linear – pm100 Mar 28 '22 at 00:56
  • 1
    Re: _"C++ STL method "find()" is used inside this loop, which may have a time complexity of O(log(N))"_, the time complexity of [`std::unordered_set::find`](https://en.cppreference.com/w/cpp/container/unordered_set/find) is required to be "Average case O(1), worst case O(b.size())." (per [unord.req](https://eel.is/c++draft/unord.req#general-176)). As some side notes, you're almost certainly using the C++ standard library, [not the STL](https://stackoverflow.com/q/5205491/11082165), and you probably don't want to include [`bit/stdc++`](https://stackoverflow.com/q/31816095/11082165) – Brian61354270 Mar 28 '22 at 01:11
  • @Brian `std::unordered_set::find` is indeed O(1), but `std::set::find` is O(log n). I can understand why OP might be confused. – Mark Ransom Mar 28 '22 at 01:38
  • Maybe this question is already discussed [here](https://stackoverflow.com/questions/65455122/whats-the-true-time-complexity-of-the-two-number-sum-problem) – GAVD Mar 28 '22 at 01:47

1 Answers1

-2

Any two numbers from n numbers can be selected in nC2 ways.

nC2 = n!/((n-2)! * 2!)

= n*(n-1)*(n-2)!/((n-2)!*2)

= n*(n-1)/2

= (n^2 - n)/2

Ignoring n and the constant 2 as it will hardly matter when n tends to infinity. The expressions finally results in a complexity of O(n^2).

Richard
  • 130
  • 5