Question

If an algorithm with an input size of n has a nested loop, and both loops make a complete pass over the input, then the performance of the algorithm will be ________.

Answer 1

Answer:

"O($n^{2}$)" is the correct answer for the above question.

Explanation:

• If an algorithm has a loop that runs n times, then the complexity of the algorithm is n times. But the above question states that the algorithm has nested for loops and every loop runs on n times.
• The nested loop means one is an inner loop that runs for the value of the outer loop.
• So if an outer loop runs on n times and for every value of outer loop the inner loop will execute, then the total execution time of the two-loop is n square ($n^{2}$).
• So the complexity of the algorithm is O($n^{2}$)