0

I am having trouble understanding this question and how to get to the answer. How do you calculate the worst case run time?

The input of the following programs is an array A containing n integers A[ 1 ] · · · A[n]. Bound the worst case run time of each program using big-O notation.

Problem 1:

i = 1, total = 0 
while i < n/2:
    total = total + A[i] 
    i=i*2

Problem 2:

total = 0
S = the set {1,2,3,4...n} 
for each subset T of S
    for each element x in T
          total = total + A[x]

Problem 3:

int i = 1, j = 1; 
    for i = 1 to n:
          while (j < n && A[i] < A[j])
             j++

The prefix sum of an array of numbers A[ 1 ], . . . , A[n] is a second array B[ 1 ], . . . , B[n] where

B[i] = summation from j=1 to i A[j]

The following problems calculate the prefix sum:

Problem 4:

for i = 1 to n: 
    B[i] = 0;
    for j = 1 to i:
          B[i] += A[j]

Problem 5:

B[1] = A[1]; 
for i = 2 to n:
      B[i] = B[i-1] + A[i]
shjshjshj
  • 1
  • 1

1 Answers1

1

Problem 1:
The algorithm performs a constant time operation (addition) at the point of each access, and that access is made while i<n/2. Since i doubles each time, the condition will no longer hold after log(n/4) steps , so the worst case time complexity is O(log(n)) (logarithmic).

Problem 2:
The algorithm accesses each element of the array (x in pseudocode) as many times as it is in a subset of S, and performs a constant time operation at the point of access. Every element is in 2^(n-1) subsets that that contain itself, and there are n such elements, so the worst case time complexity is O(n * 2^(n)) (exponential).

Problem 3:
Observe that at every time the condition in the while loop is checked, the value of i+j increases by 1, and the value of i+j can never decrease. Since i+j starts at 2 and can never go past 2n+1, the overall complexity of the algorithm is O(n) (linear).

Problem 4:
For a given value of i, the inner loop runs i times. Further, i ranges from 1 to n, so we perform 1+2+3+...+n = n(n+1)/2 constant-time computations (additions), so the overall complexity of the algorithm is O(n^2) (quadratic).

Problem 5:
The algorithm accesses n-1 elements of the array, and performs a constant time operation at the point of each access (addition), so the worst case time complexity is O(n) (linear).

Globe Theatre
  • 340
  • 1
  • 9