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.
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!
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments