Member Avatar for Gotcha

I would like to know if anyone could teach me how to solve this type of Mathematical functions: Finding the Big Oh for the following two.
Thanks for any suggestions.

f(n) = 2 + 4 + 8 + . . . + 2^n


f(n) = n!

  • 3 Contributors
  • 2 Replies
  • 107 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by Daishi

Dani AI

Generated

For : short, precise classifications and why they hold.

The sum of powers of two has the closed form sum_{i=1}^n 2^i = 2^{n+1} - 2. That expression is Theta(2^n), so the tight asymptotic class is Theta(2^n) (and therefore O(2^n)). See Geometric series for the general formula.

A simple bounding argument that gives the Theta result: the largest term 2^n is at most the whole sum, and the sum of all earlier terms is strictly less than 2^n, so
2^n <= sum_{i=1}^n 2^i <= 2^{n+1}.
Those constant-factor bounds (1 and 2) show the sum grows proportionally to 2^n.

For n! the right way to think is via Stirling's approximation:
n! ~ sqrt(2*pi*n) * (n/e)^n.
This makes two points clear: (1) n! grows far faster than c^n for any fixed c (it is superexponential), and (2) it is still bounded above by n^n. A handy elementary lower bound is n! >= (n/2)^{n/2} for n >= 2 (pair factors), which already rules out any polynomial or fixed-base-exponential as a tight upper bound. See Stirling's approximation.

As noted, the factorial case is the one that "explodes" quickly; and as observed, writing f(n) = O(f(n)) is true but tautological—use Theta or the inequalities above for useful classification. For a refresher on notation see Big O notation.

Recommended Answers

All 2 Replies

Member Avatar for Rashakil Fol

There are many 'big Oh's for these functions. In particular, in each case, f(n) is in O(f(n)).

Member Avatar for Daishi

The first one is obviously a geometric series, google is your friend if you haven't had that level of math yet.

Don't mess with the second one. n! is O(n!), and it is also O(n^n) (but not Big-Theta of n^n).

-Fredric

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.