Question

Finding Big-O of nested for/while loops (to n)

a. O(n^2)
b. O(n log n)
c. O(n)
d. O(log n)

Answer 1

The Big-O notation measures the complexity of an algorithm in terms of the input size. When analyzing nested for/while loops, the complexity is usually determined by the number of iterations. The correct answer is O(n^2), indicating quadratic complexity.

Step-by-step explanation:

The Big-O notation measures the complexity of an algorithm in terms of the input size. When analyzing nested for/while loops, the complexity is usually determined by the number of iterations. In this case, the nested loops iterate n times, resulting in a total of n * n iterations.

Therefore, the correct answer is a. O(n^2). This means that the algorithm has quadratic complexity, where the runtime grows exponentially with the size of the input.

Other possible answer choices for nested loops could be O(n log n) if the inner loop halves in size with each iteration, O(n) if the loops have linear complexity, or O(log n) if the loops have logarithmic complexity.