An algorithm is made up of 2 modules M1 and M2 . If time complexity of modules…
2014
An algorithm is made up of 2 modules M1 and M2 . If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is
Answer: B. max (h(n), g(n)) — Answer: The time complexity is Theta(max(h(n), g(n))). If the two modules run sequentially, the exact total running time is h(n) + g(n). Asymptotically, a sum…
- A.
min (h(n), g(n))
- B.
max (h(n), g(n))
- C.
h(n) + g(n)
- D.
h(n) * g(n)
Attempted by 867 students.
Show answer & explanation
Correct answer: B
Answer: The time complexity is Theta(max(h(n), g(n))).
If the two modules run sequentially, the exact total running time is h(n) + g(n).
Asymptotically, a sum of two functions equals the larger one up to constant factors: h(n) + g(n) = Theta(max(h(n), g(n))).
Example: if h(n) = n^2 and g(n) = n, then h(n) + g(n) = n^2, so the complexity is n^2 which is the maximum of the two.
Notes on different compositions:
Sequential composition: add the times, which simplifies to Theta(max(h,g)).
Nested composition: multiply the times (h(n) * g(n)) if one module invokes the other for each of its steps.
Parallel execution on ideal hardware: the time is the maximum of the two runtimes, assuming perfect parallelism and no overheads.