CODEWITHSUNDEEP
time-complexitybig-o
Jennifer
Jennifer

Reputation: 115

Time complexity of this algorithm using Big-O notation


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.

Upvotes: 1

Views: 200

Answers (1)

SomoKRoceS
SomoKRoceS

Reputation: 3063

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.

Upvotes: 2

Related Questions