Time complexity of this algorithm using Big-O notation

Question

I have to find the time complexity of the pseudocode I have created and specify it using the Big-O notation. The problem is that I don't know how to calculate it when I have an if-statement inside nested for-loops.
Here is my pseudocode, what is in brackets is the number of operations:

Algorithm largestProduct(A)
  Input array A
  Output largest product value of two elements in array A, the values and their indices
  index1 ← 0                                          (1)
  index2 ← 0                                          (1)
  n ← A length                                        (1)
  max ← 0                                             (1)
  for i ← 0 to n-1 do                                 (n)
    for j ← i + 1 to n do                             (n^2)
      if max < A[ i ] * A[ j ] then                   (?)
        max ← A[ i ] * A[ j ]
        index1 ← i
        index2 ← j
  return max, A[index1], index1, A[index2], index2

Thank you in advance for your help.

SomoKRoceS · Accepted Answer · 2020-09-25 00:23:17Z

2

Since the operations inside the if statement and its condition do not affect the number of the iterations and they are single operations (constant), then you can consider the if statement as an O(1).

It is true that the nested for loops do O(n^2) iterations, therefore, there are constant amount of operations running O(n^2) times, makes it O(n^2)*O(1)=O(n^2) overall.

edited Sep 25, 2020 at 0:23

answered Sep 25, 2020 at 0:22

SomoKRoceS

3,0733 gold badges24 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time complexity of this algorithm using Big-O notation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related