What is the runtime in Theta notation of the following program: import java.util

Question

What is the runtime in Theta notation of the following program:

import java.util.Arrays; public class MaximumSubArrayDP { //bottom up approach public int solve(int [] a){ int [] solution = new int[a.length+1]; solution[0] = 0; for (int j = 1; j <solution.length ; j++) { solution[j] = Math.max(solution[j-1]+a[j-1],a[j-1); } //this will print the solution matrix //System.out.println(Arrays.toString(solution)); //now return the maximum in the solution array int result = solution[0]; for (int j = 1; j <solution.length ; j++) { if(result<solution[j]) result = solution[j]; } return result; } public static void main(String[] args) { int arrA[] = { 1, 2, -3, -4, 2, 7, -2, 3 }; MaximumSubArrayDP i = new MaximumSubArrayDP(); System.out.println("Maximum subarray is " + i.solve(arrA)); } }

Explanation / Answer

The runtime complexity of the code is theta(n).

where n is the lenght of the input array.

This is because we are using only two for loop in the code:

Both the for loop runs n times.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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