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

**prefix sum**,

**scan**, or

**cumulative sum**of a sequence of numbers

*x*

_{0},

*x*

_{1},

*x*

_{2}, ... is a second sequence of numbers

*y*

_{0},

*y*

_{1},

*y*

_{2}, ..., the sums of prefixes (running totals) of the input sequence:

*y*_{0}=*x*_{0}*y*_{1}=*x*_{0}+*x*_{1}*y*_{2}=*x*_{0}+*x*_{1}+*x*_{2}- ...

**input numbers**1 2 3 4 5 6 ... **prefix sums**1 3 6 10 15 21 ...

- if (n==1) do nothing and return
- Do in parallel
- make recursive call for prefix_compute(A[1], A[n/2])
- Make recursive call for prefix_computer(A[n/2+1],A[n])
- for each A[n/2+1] do A[i] = A[i] + A[n/2]

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) + nIn this case you have^{c}

- a = 1
- b = 2
- c = 0

_{b}a (since 0 = log

_{2}1), you are in case two of the Master Theorem, which solves to Θ(n

^{c}log n) = Θ(n

^{0}log n) = Θ(log n).

## 0 comments:

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