Big Omega or so called asymptotic upper bound of algorithms such as Sequential statements, If statements and Looping construct

(i) Sequential statements:

Big Omega of this algorithm equals to maximum time complexities of all individual statements (i.e. sum of maximum time complexities of the individual statements)

Therefore, O[g(n)] = O{f1(n)+f2(n)+ ... +fk(n)}

Conclusion: Overall complexity of this algorithm equates to O[g(n)]

(ii) If statements:

Big Omega of this algorithm equals to maximum time complexities of either one of the alternative statements i.e. then branch -> f(n)/else branch -> g(n)

Therefore, O[h(n)] = O{f(n), g(n)}

Conclusion: Overall complexity of this algorithm equates to O[h(n)]

(iii) Looping construct:

Big Omega of this algorithm equals to aggeration of the maximum time complexities of the following: (a) execution time (i.e. elementary operations execution in a given iteration) -> f(n) and (b) the number of iterations -> g(n)

Therefore, O{f(n) * g(n)}

Conclusion: Overall complexity of this algorithm equates to O{f(n) * g(n)}

## Wednesday, February 11, 2009

### Time complexity of algorithms - In particular Big Omega of algorithms

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment