CODEWITHSUNDEEP
c++time-complexityspace-complexity
James Franco
James Franco

Reputation: 4706

Understanding the time and space complexity of this problem

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]);
    }

}

Upvotes: 1

Views: 126

Answers (1)

jwezorek
jwezorek

Reputation: 9535

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).

Upvotes: 2

Related Questions