Java - Analyze each algorithm according to the points as follows: 1. Choose the

Question

Java -

Analyze each algorithm according to the points as follows:
1. Choose the input size n and explain your choice.
2. In each case T(n) denotes the running time (number of steps) of
the algorithm. Compute T(1) and T(2)
3. Compute and estimate T(n) in terms of the O(n) scale. Use the
simplest and possibly the smallest valid big-Oh expressions.
4. If it applies, point out your estimates both for the worst case and
best case.
5. Document and comment the methods in Exercises 1 – 4. Describe
the tasks of the methods, explain the meaning the return value if
applies, show and justify your big-Oh estimate.
6. It is not necessary to run these methods in actual programs, but if
the task it performs is dubious, testing the method with various
input in actual applications of the code may help to find its
purpose and the big-Oh estimate

------

int occurrences( int[] list, int element ){
int answer = 0;
for(int k = 0; k < list.length; k++ )
if (element == list[k])
answer++;
return answer;
}//end method
Comments:

Explanation / Answer

1. We can take any positive non zero input size, n in order to see this algorithm work. For n = 0, this algorithm just returns 0 without the loop iterating even once. (3 steps)

2.

int occurrences(int[] list, int element) {

// Let n = list.length

int answer = 0; // 1 STEP

for(int k = 0; k < list.length; k++) // n + 1 STEPS

if (element == list[k]) // n STEPS

answer++; // n STEPS

return answer; // 1 STEP

}

Summing up we have,

T(n) = 1 + n + 1 + n + n + 1 = 3(n + 1)

So, T(1) would be 6 STEPS and T(2) would be 9 STEPS.

3. This time we calculate the time taken, by multiplying an arbitrary constant to the number of steps

int occurrences(int[] list, int element) {

// Let n = list.length

int answer = 0; // c1

for(int k = 0; k < list.length; k++) // c2 * (n + 1)

if (element == list[k]) // c3 * n

answer++; // c4 * n

return answer; // c5

}

Summing up we have,

c * T(n) = c1 + c2 * (n + 1) + c3 * n + c4 * n + c5

c * T(n) = (c1 + c2 + c5) + (c2 + c3 + c4) * n

T(n) = (constant) + (constant) * n = O(n)

Hence O(n) is the compexity of the code.

4. The best case and the worst case of the problem will be the same because for each input steps proportional to n are required. Hence O(n) would be the complexity.

5. The return valuse contains the count of the number of elements matched in the array.

6. The purpose of this program is to count the number of occurences of an element in an array and the complexity is O(n).

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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