Difference between revisions of "TADM2E 2.21"
From Algorithm Wiki
| Line 22: | Line 22: | ||
Edit on Edit: The mistake here is that <math>n^{-1/2} = \dfrac{1}{\sqrt{n}}</math> and not <math>\sqrt{n}</math>. | Edit on Edit: The mistake here is that <math>n^{-1/2} = \dfrac{1}{\sqrt{n}}</math> and not <math>\sqrt{n}</math>. | ||
| − | Since <math>\dfrac{1}{\sqrt{n}}</math> grows slowly compared to <math>log n</math>, the answer is False. | + | Since <math>\dfrac{1}{\sqrt{n}}</math> grows slowly compared to <math>\log n</math>, the answer is False. |
Revision as of 19:02, 22 November 2018
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.
Edit on Edit: The mistake here is that $ n^{-1/2} = \dfrac{1}{\sqrt{n}} $ and not $ \sqrt{n} $. Since $ \dfrac{1}{\sqrt{n}} $ grows slowly compared to $ \log n $, the answer is False.
