Assume that f(n) goes to infinity as n goes to infinity.

This is a homework problem and I would appreciate an idea/guidance instead of the complete answer.

Assume that f(n) goes to infinity as n goes to infinity. This is a homework problem and I would appreciate an idea/guidance instead of the complete answer. |

This isn't true. Consider the function f(n) = n! as a counterexample, which definitely goes toward infinity as n goes to infinity. We can prove, though, that n! ? O((n - 1)!). The proof is by contradiction. Suppose that n! = O((n - 1)!). Then there exists some n In case you're wondering how I came up with this: my idea was to find a function that grows so rapidly that no matter what constant you picked, the ratio between f(n + 1) and f(n) would eventually get so large that it would exceed that constant. It just happened to be the case that n! fit the bill. In retrospect, I should have remembered that n! ? O((n - 1)!) because many algorithms have runtimes like O((n + 1)!), which doesn't simplify down to O(n!). Hope this helps! |

- Prove max(O(f(n)), O(g(n)))=O(max(f(n), g(n))
- Complexity of f(n) = b*n+f(n-1)
- prove n = Big-O(1) using induction
- How can I prove 1/n is O(1)?
- How to prove max number of connection between n nodes is n*(n-1)/2
- Prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices [closed]
- Prove or disprove n^2 - n + 2 ? O(n)
- Prove that n! is not in O(n^p) for any constant natural number p
- F#: always “unexpected 'when' keyword”
- Is the Turtle and Rabbit algorithm always O(N)?
- Saxon Unexpected token “ < e o f >”
- Big O of f(n) = N! + 2^N
- Generating M distinct random numbers (one at a time) from a given range 0..N-1 in less than O(M) memory
- How do i prove (n^2 - n)/2 is O(n^2)? [closed]
- Prove the number of binomial trees in a binomial heap with n elements is at most O(log n)

© Copyright ask.programmershare.com.

Design by ask.programmershare.com

## comments: