0

I have a program below which calculates the Maximum Pairwise Product.

for i in range(n):
    for j in range(i + 1, n):
        product = max(product, a[i] * a[j])

As per my calculation the above program takes (n^2 - n) steps where n is the number of elements but the book I am following it says n^2 steps. Can anyone help me in understanding which is right?

mkrieger1
  • 19,194
  • 5
  • 54
  • 65
nano
  • 17
  • 1
  • 5
  • You are both right. But your calculation is not complete: `n^2-n` is of `O(n^2)` complexity. – Michael Szczesny Oct 31 '20 at 13:26
  • Thank you for your comments @MichaelSzczesny. Can you please elaborate a bit more? – nano Oct 31 '20 at 13:28
  • 1
    Does this answer your question? [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) – mkrieger1 Oct 31 '20 at 13:30

2 Answers2

2

In Big O Notation, the Maximum Degree term of the equation is considered only. For eg,

1)n+7 - here we will consider n only so O of n is the time complexity.

2)n^2 + n + 3 - here we will consider n^2 only so O of n^2 is the time complexity.

3)3x(n^2) - here we will consider n^2 only so O of n^2 is the time complexity.

As big O notation is the approximate time complexity, we neglect all the small terms.

For your equation n^2 - n

Consider n as 10000

n^2 = 100000000

n^2 - n = 99990000. Which is nearly equal to 100000000 i.e n^2

so we consider the highest degree term only. Therefore time complexity is O(n^2)

Vishal_898
  • 300
  • 1
  • 9
1

When dealing with the Big O notation you always take the largest power terms - the logic is simple - as n grows larger n^2 is going to grow quicker than n and therefore the growth rate of the time will be dominated by n^2.

Therefore the correct big O is O(n^2)

Tony Suffolk 66
  • 9,358
  • 3
  • 30
  • 33