What do You mean by prefix Computation? Compute its time complexity.

In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence:
y0 = x0
y1 = x0 + x1
y2 = x0 + x1+ x2
For instance, the prefix sums of the natural numbers are the triangular numbers:
input numbers  1  2  3  4  5  6 ...
prefix sums  1  3  6 10 15 21 ...
This problem can be solved by using divide and conquer method. The pseudo-code for this is given below:
  1. if (n==1) do nothing and return
  2. Do in parallel
    1. make recursive call for prefix_compute(A[1], A[n/2])
    2. Make recursive call for prefix_computer(A[n/2+1],A[n])
  3. for each A[n/2+1] do A[i] = A[i] + A[n/2]
Here, Step 1 takes O(1) and Step 2 takes T(n/2) since two recursive calls are made to two subsets. Also, in step 3, second half of the processor, i.e. subset 2 reads the global value of A[n/2] concurrently and update their answer. This takes O(1).

Hence, Time complexity is given by T(n) = T(n/2) + O(1). Solving this my Master theorem method, we have,
T(n) = T(n / 2) + O(1)
Since the Master Theorem works with recurrences of the form
T(n) = aT(n / b) + nc
In this case you have
  • a = 1
  • b = 2
  • c = 0
Since c = logba (since 0 = log2 1), you are in case two of  the Master Theorem, which solves to Θ(nc log n) = Θ(n0 log n) = Θ(log n).


Feel free to contact the admin for any suggestions and help.