TADM2E 2.21 - Revision history

Kelvinjhwong: I added the 'Addendum on Edit on Edit'

2018-11-28T04:52:33Z

I added the 'Addendum on Edit on Edit'

Ashmew2 at 19:02, 22 November 2018

2018-11-22T19:02:11Z

Ashmew2 at 19:01, 22 November 2018

2018-11-22T19:01:01Z

Ashmew2 at 18:44, 22 November 2018

2018-11-22T18:44:57Z

Ifeins: Pointing up a possible mistake

2018-11-11T18:26:14Z

Pointing up a possible mistake

Algowikiadmin: Recovering wiki

2014-09-11T18:14:05Z

Recovering wiki

New page

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

← Older revision		Revision as of 04:52, 28 November 2018
Line 23:		Line 23:
	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.
		+
		+	(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)

← Older revision		Revision as of 19:02, 22 November 2018
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.

← Older revision		Revision as of 19:01, 22 November 2018
Line 21:		Line 21:
	Then 7 should be True.		Then 7 should be True.

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

← Older revision		Revision as of 18:44, 22 November 2018
Line 20:		Line 20:

	Then 7 should be True.		Then 7 should be True.
		+
		+	The mistake here is that <math>n^{-1/2} = \dfrac{1}{\sqrt{n}}</math> and not <math>\sqrt{n}</math>

← Older revision		Revision as of 18:26, 11 November 2018
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.