239 views

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

1. $O(n^3)$
2. $\Omega(n^3)$
3. $\Omega(n \log n)$
4. $\Theta(n^6 \log n)$

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.

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