Subject | Algorithm Design |
---|---|

NU Year | Set: 2.(a) Marks: 5 Year: 2009 |

**asymptotic lower bounds**, since it bounds the growth of the running time from below for large enough input sizes.

f(n) = 8n^3+2n^2

g(n) = n^3

From definition, we know f(n) = Theta(g(n)) if and only if f(n) = O(g(n)) and

f(n) = Omega(g(n)).

So, we need to show f(n)= O(g(n)) and f(n) = Omega(g(n))

f(n) = O(g(n)) : if there are positive constants c and n_{o }such that f(n) <= c(g(n)) when n >= n_{o}

8n^3+2n^2 <= c(g(n))

when c = 9, n_{o} = 2, for all n>=n_{o} 8n^3+2n^2 <= 9 (n^3)

Therefore, f(n) = O(g(n))

f(n) = Omega (g(n)) : if there are positive constants c and n_{o} such that f(n) >= c(g(n)) when n>=n_{o}

8n^3+2n^2 >= c(n^3)

when c = 8, n_{o} = 0, for all n>=n_{o} 8n^3+2n^2 >= 8(n^3)

Therefore, f(n) = Omega(g(n))

Therefore, 8n^3+2n^2 = Theta (n^3).