Find the running time T( n ) of the calculateSum method: public static int calcu

Question

Find the running time T( n ) of the calculateSum method:

public static int calculateSum(int[] numbers) {

int sum = 0;

for(int i=0; i<numbers.length; i++) {

sum += numbers[i];

}

return sum;

}

Note that you are finding the running time, not the order of growth. We already know the order of growth is O( n ).

List the steps leading to your calculation in case your answer is wrong but could get partial credit.

Count all operations, including loop controls, declarations, and updates.

i++ should be considered two statements (an addition and assignment)

Hint: re-write using "statement1, statement2, etc." as shown in the reading for this week.

Explanation / Answer

let us assume, intialization takes 1 sec, adding takes 1 sec, return takes 1 sec and increment takes 1 sec.

So, outside for loop, we have 2 operations, initialization of sum and return of sum. So, both operations collectively take 2 sec.

In for loop, in each iteration, we will have

1 comparison operation, 1 increment operation, 1 addition and 1 assignment operation. Along with that array length is calculated each time. Since the array is of length 'n' (say). Therefore, the total time taken by for loop is 5n + 1 (initialization of i at starting of loop, it is done only one time).

So, total running time = 2 + 5n + 1 = 5n + 3.

Hope it helps, do give your valuable response.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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