Answer to Question #218410 in Algorithms for Tony

Question

1.

Derive the best and worst-case time complexity for the following algorithm and express it in O notation. (Here max and min functions assume their usual meaning.)

1.

myFunction(A[ ]) {

2.

n = A.length

3.

v = n

4.

for i = 1 to n {

5.

v = min(A[i], v)

}

6.

v = max(1, n)

7.

for j = 1 to 100 {

8.

sum = 0

9.

k = 1

10.

while k <= v {

11.

sum = sum + A[k]

12.

k = k*2

}

}

}

Hints: Find out the greatest and smallest possible value for v, and use it in your analysis.

Answer 1

The given code is

myFunction(A[ ]) {
n = A.length;
v = n;
for (i = 1 to n ){
v = min(A[i], v)
}
v = max(1, n)
for (j = 1 to 100) {
sum = 0
k = 1
while (k <= v) {
sum = sum + A[k]
k = k*2
}
}
}

For the best case n=1, it will found the minimum vertex and 100O(1)

For the worst case n, it will found maximum 100 * O(n)