GATE Overflow | Algorithms | Test 1 | Question: 9

Question

Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is

• A. $O(n^3)$
• B. $\Omega(n^3)$
• C. $\Omega(n \log n)$
• D. $\Theta(n^6 \log n)$

Answer 1

Complexity of algorithm determined by slowest program fragment.
So it will be $O(n^3)$ and we can not select $\Omega(n^3)$ in absence of lower bound data.

Comments

how can we be sure if the segments are not interlinked ?

---

I am a bit confused...does the problem statement imply that the program has only the given 3 steps?...I was thinking of an option like 'information insufficient'.

---

@Arjun sir what if these are nested steps , the question does not explicitly say that these are independent steps