Search code examples
runtimebig-oanalysisgomega

Can Someone Verify My Answers on Asymptotic Analysis?

This for a data structures and algorithms course. I am confident in all of them but part d and I am not sure how to approach e. I know for part e, it is the sum of the harmonic series, and our professor told us it is bounded by (ln(n) + 1/n, ln(n) + 1) since there is no closed form representation for the sum of the harmonic series, but I am still not sure how to realize which has the faster or slower growth rate to determine how to classify them. If someone could review my answers and help me understand part e, I would appreciate it. Thank you.

The question: https://i.sstatic.net/34D7d.jpg My answers: https://i.sstatic.net/aEHrA.jpg

Solution

  • Any function of the form <code>n^a a > 0</code> is going to dominate a series like that. We can factor out the constant to see that a bit easier and such a general harmonic series is bounded above by log.

    enter image description here

    So obviously we can ignore the 200 in big-O. In lieu of a proof since it seems one isn't required you can think about the intuition behind it. The summation as n grows will keep adding smaller and smaller terms but n^a is going to keep growing to the point where enter image description here is massive but 1/n is practically zero.