For `for i = 1 to n: sum = sum + i`, the total operation count is approximately
Aa linear function of n (something like 3n + 1)
Bconstant, independent of n
Cn² because the loop body has two operations
Dn log n because addition is logarithmic
Answer & Solution
Correct answer: A. a linear function of n (something like 3n + 1)
The loop runs n times, each iteration doing constant work (comparison, addition, store). Total is roughly 3n + 1. The dominant term is n, so the function is linear. n² would require nested looping, n log n is from divide-and-conquer, constant would require the loop count not depending on n.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for