c++ - Filling an array in such a way that each element equal to minimum sum of two numbers such that -

c++ - Filling an array in such a way that each element equal to minimum sum of two numbers such that -

given array (contains positive integers) has first k elements: a1, a2, .... ak. need fill remaining (n - k) elements (the array has n elements in total). value of n 10 ^ 3 , 1 <= k <= n. value of each ai minimum sum of 2 numbers such sum of positions of 2 numbers equal i. here pseudocode (my algorithm):

for = k + 1 n a[i] = max_value j = 1 (i / 2) a[i] = min(a[i], a[j] + a[i - j])

time complexity: o(n ^ 2) question: there other way faster? i'm looking info structures or algorithms can find value of each ai in less o(n). p/s: procedure in programme need fast possible.

you increment programme speed using threads run check minimum value in parallel. illustration run 4 threads each of checks 1/4 of range of j. improve speed marginally, algorithm still take o(n^2) running time.

i agree comment can't beyond o(n^2). best bet seek things optimize code cut down coefficient in front end of n^2.

c++ arrays algorithm data-structures