1

I'm trying to find the time complexity of the following function:

for (int i = 0; i < arraySize; i++) { 
    for (int j = 0; j < arraySize; j++) { 
        if (array[j] < array[i]) { 
            //Do something
        }
        else if (array[j] == array[i]) { 
            //Do something else 
        }
    }
}

I think it is O(n^2), but I'm not sure how to prove it.

Anoop H.N
  • 1,244
  • 1
  • 15
  • 31
Michael Depaye
  • 11
  • 3

1 Answers1

2

You are correct. It is O(n^2).

Rule of thumb: Simple programs can be analyzed by counting the nested loops of the program. A single loop over n items yields f( n ) = n. A loop within a loop yields f( n ) = n^2. A loop within a loop within a loop yields f( n ) = n^3.

You can also check with the link below for,

How to find time complexity of an algorithm

Hope this helps!

Community
  • 1
  • 1
Anoop H.N
  • 1,244
  • 1
  • 15
  • 31