TADM2E 2.21

From Algorithm Wiki
Revision as of 18:44, 22 November 2018 by Ashmew2 (talk | contribs)
Jump to: navigation, search

First we should see the dominance relations given in the book as it will help in determining the complexity for cases involving square root of n.

1. True 2. False, sqrt(n) dominates logn. 3. True 4. False 5. True 6. True 7. False


Edit: I'm not sure why (7) is False. It's possible that I'm mistaken but I think that:

$ n^{-1/2} = \dfrac{n}{\sqrt{n}} = \sqrt{n} $

Since a square root of N dominates logn:

$ \log n = O(\sqrt{n}) $

Then 7 should be True.

The mistake here is that $ n^{-1/2} = \dfrac{1}{\sqrt{n}} $ and not $ \sqrt{n} $