Get the Asymptotic Notation of The Run time

Question

I have the runtime below:

  T(n) = (1- (1/2^n)) ((n+1)/2)

I know its upperbound can be something like : O(2^n)

But I couldn't find its lowerbound or omega. Is it possible that an algorithm has no lower bound? What about theta ? little oh and little omega?

Answer 1

The inverse exponential is negligible in front of 1, so Θ(n), which implies all other bounds.

Answer 2

As 1- 1/2^n >= 0.5 for all n >= 1, we can say T(n) >= 0.5(n+1)/2 = (n+1) /4. Hence, T(n) = \Omega(n). Also, as 1- 1/2^n < 2 for all n >= 0, T(n) <= n + 1 we can say T(n) = O(n). Therefore, we can say T(n) = \Theta(n).