contestada

What is the tightest bound big-Oh (O) time complexity for the following code in terms of input size n? Show all necessary steps:
Algorithm MyAlgorithm (A,B)
Input: Arrays A and B each storing n >= 1 integers.
Output: What is the output? (Refer to part b below)
Start:
count = 0
for i = 1 to n*n do {
sum = 0
for j = 1 to i do {
sum = sum + A[0]
for k = 1 to j do
if (k <= n-1)
sum = sum + A[k]
}
if (i < n)
if B[i -1] <= sum then count = count + 1
}
return count

(I'M CONFUSED BETWEEN O(n^4) and O(n^6))

Respuesta :

KatoSazu

Answer:

1. The outer loop iterates from 1 to n*n, which means it runs n*n times.

2. Inside the outer loop, there is an inner loop that iterates from 1 to i, which runs i times. Since i can vary from 1 to n*n, the total number of iterations of the inner loop is (n*n)*(n*n+1)/2 ≈ (n^4)/2.

3. Inside the innermost loop, there are constant operations (e.g., addition and comparison) that are executed in a fixed amount of time regardless of the input size.

Considering the above analysis, the algorithm has a time complexity of O(n^4) because the dominant factor that affects the running time is the innermost loop, which has (n^4)/2 iterations. Thus, the tightest bound big-Oh time complexity for this code is O(n^4).

Otras preguntas