Prove that the sum ak logkn + ak−1logk−1n +···+ a0 is asymptotically bounded above by O(logk n).  Prove that O(n/ log n) processing units suffice to sum up n numbers in O(log n) parallel time. Hint:...

Prove that the sum ak logkn + ak−1logk−1n +···+ a0 is asymptotically

bounded above by O(logk n).

 Prove that O(n/ log n) processing units suffice to sum up n numbers in O(log n)

parallel time. Hint: Assume that the numbers are summed up with a tree-like

parallel algorithm described in Example 2.1. Use Brent’s Theorem with W =

n − 1 and T = log n and observe that by reducing the number of processing units

to p := n log n, the tree-like parallel algorithm will retain its O(log n) parallel

time complexity.