# Difference between revisions of "TADM2E 2.21"

(Recovering wiki) |
Kelvinjhwong (Talk | contribs) m (I added the 'Addendum on Edit on Edit') |
||

(4 intermediate revisions by 2 users not shown) | |||

Line 8: | Line 8: | ||

6. True | 6. True | ||

7. False | 7. False | ||

+ | |||

+ | |||

+ | Edit: I'm not sure why (7) is False. | ||

+ | It's possible that I'm mistaken but I think that: | ||

+ | |||

+ | <math>n^{-1/2} = \dfrac{n}{\sqrt{n}} = \sqrt{n}</math> | ||

+ | |||

+ | Since a square root of N dominates logn: | ||

+ | |||

+ | <math>\log n = O(\sqrt{n})</math> | ||

+ | |||

+ | Then 7 should be True. | ||

+ | |||

+ | 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. | ||

+ | |||

+ | (Addendum on Edit on Edit: <math>\dfrac{1}{\sqrt{n}}</math> doesn't grow at all, it tends to zero as n goes to positive infinity) |

## Latest revision as of 04:52, 28 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.

(Addendum on Edit on Edit: $ \dfrac{1}{\sqrt{n}} $ doesn't grow at all, it tends to zero as n goes to positive infinity)