Question L[20 points] For each of the following four program fragments, give an

Question

Question L[20 points] For each of the following four program fragments, give an analysis of the running time in terms of Big-O. Your answer will be a very short statement T(n) O(?) Your algorithm run time analysis should only contain the highest term when writing in terms of Big O For example: TN)-O(n +5n2) would be incorrect, it should be simplified (dropping the lowest terms) and written as: TN)-O(n') TON-? sum = 0; for i = 1 to N do sum = sum + i; TN) (b) sum = 0; for i 1 to N do for j = 1 to N do for k = 1 to N do sum = sum + 1;

Explanation / Answer

[1a]
Time complexity of nested loops is equal to the number of times the innermost statement is executed.
Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount
Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.

O(N) = T(N)

[1b]

O(N^3) = T(N^3)

[1c]

O(N^3) = T(N^3)

[1d]
O(N^2) = T(N^2)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.