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 x₀, x₁, x₂, ... is a second sequence of numbers y₀, y₁, y₂, ..., the sums of prefixes (running totals) of the input sequence:

y₀ = x₀

y₁ = x₀ + x₁

y₂ = x₀ + x₁+ x₂

...

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) + n^c

In this case you have

• a = 1
• b = 2
• c = 0

Since c = log_ba (since 0 = log₂ 1), you are in case two of  the Master Theorem, which solves to Θ(n^c log n) = Θ(n⁰ log n) = Θ(log n).