0

I only ask this question because my instructor hardly taught us about Big O notation or how to find time/step complexities within code.

Give the step complexity in Big O natation of the following code snippet:

int Bar(std::vector<int> x, std::vector<int> y) {
    int answer = 0;
    // Assume x.size() == y.size()
    if (x.size() != y.size()) {
        throw std::runtime_error(“x and y size mismatch”);
    }
    for (int i = 0; i < x.size(); i++) {
        for (int j = 0; j < y.size(); j++) {
            answer += x.at(i) * y.at(j);
        } 
    }
    return answer;
}

If anyone can explain Big O notation and how to approach this problem, it would be greatly appreciated.

user15397522
  • 25
  • 2
  • This would be `O(mn)`, where `n` is the size of `x`, and `m` is the size of `y`. The reason why is simply you do an operation for a nested loop where the outer loop is size `n` (O(n)), and the inner loop is size `m` (O(m)). Since you do a size `m` loop for each loop in `n`, the two are multiplied together. So, the total complexity is `O(mn)`. Now, you can do this way faster, but as the algorithm is written, it's that time complexity. – Alex Huszagh May 12 '21 at 01:43
  • 1
    Some handy reading: [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – user4581301 May 12 '21 at 02:02

0 Answers0