Discussion
Consider the following segment of a parallel algorithm expressed in PRAM model of computing and allows concurrent read exclusive write model. What is the "Parallel time" complexity ?
For k = m - 1 step - 1 to 0 do
for all j, \(2^{k} \le j \le 2^{k+1} - 1\), in parallel do
A(j) = max {A(2j), A(2j + 1)}
where "max" is a function that find maximum of two numbers using single comparison operation.
Answer: C
The parallel time is \(O(\log_2 n)\).
The algorithm finds the maximum of the \(n = 2^{m}\) values stored in a complete binary tree, level by level from the bottom. In each iteration of the outer loop, all nodes on level k compute the maximum of their two children in parallel, using one comparison, so each iteration takes constant time.
The outer loop runs once per level, m times, and \(m = \log_2 n\), so the parallel time is \(O(\log_2 n)\). O(n) or worse would be the sequential cost of scanning the values.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development