1

I have the following code. I have been told that the time complexity of this is O(n). But I am having a hard time understanding how. To me it seems like it is O(n) + O(n) + O(n) = O(3n) and the space complexity is O(3n) as well because 3 vectors that get populated to the size of n. Is my understanding correct ?

void productofself(std::vector<int> v)
{
    int multipliedProduct = 0;
    std::vector<int> left;
    std::vector<int> right(v.size());
    std::vector<int> result;
    for (int i = 0; i < v.size(); i++)
    {
        if (i == 0) 
        { 
            multipliedProduct = 1; 
        }
        else 
        {
            multipliedProduct *= v[i - 1];
        }
        left.push_back(multipliedProduct);
    }
   
    for (int i = v.size() - 1; i >= 0; i--)
    {
        if (i == v.size() - 1) 
        {
            multipliedProduct = 1;
        }
        else
        {
            multipliedProduct *= v[i + 1];
        }

        right[i]=multipliedProduct;
    }


    for (int i = 0; i < v.size(); i++)
    {
        result.push_back(left[i] * right[i]);
    }

}
James Franco
  • 4,516
  • 10
  • 38
  • 80
  • 5
    Constant get removed from big-O since they don't actually matter. We use it to describe how the algorithm scales, not its actual performance. – NathanOliver Jun 22 '21 at 21:47
  • 1
    related/dupe: https://stackoverflow.com/questions/25777714/which-algorithm-is-faster-on-or-o2n – NathanOliver Jun 22 '21 at 21:51
  • O(n) and O(3n) are the same thing. Both mean (in your case) that time and space each increase linearly with n (in the asymptotic case i.e. as n gets large). – Peter Jun 23 '21 at 06:49

1 Answers1

2

I think you are missing the point of the asymptotic notation. That code is O(3n) but it is also O(n) and the latter is what matters.

O(3n) and O(n) are equivalent by definition.

We say f(x) is O( g(x) ) if there exist two constants m and k such that f(x) < m * g(x) for all x greater than k. Basically f(x) is O(g(x)) if for sufficiently large x, f(x) is always smaller than a constant factor times g(x).

So you can see the constant factor right in that definition: m. A scaling factor like 3 comes out in the wash. There exists an m such that 3 * n < m * n, namely any number greater than 3. So the function f(n) = 3*n is O(n).

jwezorek
  • 8,592
  • 1
  • 29
  • 46