Algorithm complexity - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:13:43Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:13, 9 October 2019
Line 413:		Line 413:
	'''Question P-3.57: Perform experimental analysis to test hypothesis that Python's sorted() function runs in O(n log n) time.'''		'''Question P-3.57: Perform experimental analysis to test hypothesis that Python's sorted() function runs in O(n log n) time.'''

	Answer: see https://charlesreid1.com~~:3000~~/cs/python/src/master/algorithm_complexity/test_sorted.py		Answer: see https://git.charlesreid1.com/cs/python/src/master/algorithm_complexity/test_sorted.py

	==Skiena Chapter 1 Questions==		==Skiena Chapter 1 Questions==

2017-05-29T07:26:27Z

Number of towns and cities in US

← Older revision		Revision as of 07:26, 29 May 2017
Line 646:		Line 646:
	Of that remaining 20%, etc.		Of that remaining 20%, etc.

	Do this multiple times, splitting into groups that live in cities of 1M, 100k, 10k, 1k, 100, and 10 ~~(Note: if you start with 10 M, it ''really'' throws off the estimate~~.) Then we get:		Do this multiple times, splitting into groups that live in cities of 1M, 100k, 10k, 1k, 100, and 10. Then we get:

	[[Image:PopCenterTable.jpg\|500px]]		[[Image:PopCenterTable.jpg\|500px]]

			'''(Note: the drawing includes cities of >10M separately from 1M, but this throws the estimate off by an order of magnitude on the small side. Not enough megacities in the US.)'''

	When we combine this with the total population of 3 M people, we get the total number of cities/towns that people live in (that is, if 80% of 300 M people live in cities of 10 M people or more, we can determine how many 10 M person cities there are; etc.)		When we combine this with the total population of 3 M people, we get the total number of cities/towns that people live in (that is, if 80% of 300 M people live in cities of 10 M people or more, we can determine how many 10 M person cities there are; etc.)

2017-05-29T06:58:50Z

2017-05-29T04:35:13Z

Estimation

2017-05-28T19:10:55Z

Number of towns and cities in US

@@ Line 670: / Line 670: @@
 This is pretty damn close to the number of "incorporated places" listed by the census: 19,354 [http://www.census.gov/popest/data/counties/totals/2012/CO-EST2012-alldata.html].
 {{CSFlag}}
 [[Category:Algorithms]]

2017-05-28T19:03:26Z

Number of towns and cities in US

← Older revision		Revision as of 19:03, 28 May 2017
Line 644:		Line 644:
	Of that remaining 20%, etc.		Of that remaining 20%, etc.

	Do this multiple times, splitting into groups that live in cities of ~~10M,~~ 1M, 100k, 10k, 1k, and ~~<1k~~, we get:		Do this multiple times, splitting into groups that live in cities of 1M, 100k, 10k, 1k, 100, and 10 (Note: if you start with 10 M, it ''really'' throws off the estimate.) Then we get:

	[[Image:PopCenterTable.jpg\|500px]]		[[Image:PopCenterTable.jpg\|500px]]
Line 665:		Line 665:
	\right)		\right)
	</math>		</math>

			Plugging this into Wolfram Alpha gives 17,040.

			This is pretty damn close to the number of "incorporated places" listed by the census: 19,354 [http://www.census.gov/popest/data/counties/totals/2012/CO-EST2012-alldata.html].

2017-05-28T19:00:08Z

Number of hours in 1M seconds

← Older revision		Revision as of 19:00, 28 May 2017
Line 630:		Line 630:

	Trick here is not to do just an order of magnitude estimate, but to make use of quarters as well. 1000/25, not just 1000/10. (If you don't do this, twice, you'll be off by an order of magnitude.)		Trick here is not to do just an order of magnitude estimate, but to make use of quarters as well. 1000/25, not just 1000/10. (If you don't do this, twice, you'll be off by an order of magnitude.)

			<br />
			<br />

			====Number of towns and cities in US====

	'''Question: Estimate the number of towns and cities in the United States.'''		'''Question: Estimate the number of towns and cities in the United States.'''

2017-05-28T18:59:32Z

Number of hours in 1M seconds

← Older revision		Revision as of 18:59, 28 May 2017
Line 645:		Line 645:
	When we combine this with the total population of 3 M people, we get the total number of cities/towns that people live in (that is, if 80% of 300 M people live in cities of 10 M people or more, we can determine how many 10 M person cities there are; etc.)		When we combine this with the total population of 3 M people, we get the total number of cities/towns that people live in (that is, if 80% of 300 M people live in cities of 10 M people or more, we can determine how many 10 M person cities there are; etc.)

	Here's the nested expression:		Here's the nested expression (p = people):

	<math>		<math>
	300 M = 3e8 ~~people~~ \times \left(		300 M = 3e8 p \times \left(
	\dfrac{.80 ~~people~~}{1e6 ~~people~~/city} + .20 \times \left(		\dfrac{.80 p}{1e6 p/city} + .20 \times \left(
	\dfrac{.80 ~~people~~}{1e5 ~~people~~/city} + .20 \times \left(		\dfrac{.80 p}{1e5 p/city} + .20 \times \left(
	\dfrac{.80 ~~people~~}{1e4 ~~people~~/city} + .20 \times \left(		\dfrac{.80 p}{1e4 p/city} + .20 \times \left(
	\dfrac{.80 ~~people~~}{1e3 ~~people~~/city} + .20 \times \left(		\dfrac{.80 p}{1e3 p/city} + .20 \times \left(
	\dfrac{.80 ~~people~~}{1e2 ~~people~~/city} + \dfrac{.20}{1e1 ~~people~~/city}		\dfrac{.80 p}{1e2 p/city} + \dfrac{.20}{1e1 p/city}
	\right)		\right)
	\right)		\right)

2017-05-28T18:58:43Z

Number of hours in 1M seconds

← Older revision		Revision as of 18:58, 28 May 2017
Line 643:		Line 643:
	[[Image:PopCenterTable.jpg\|500px]]		[[Image:PopCenterTable.jpg\|500px]]

			When we combine this with the total population of 3 M people, we get the total number of cities/towns that people live in (that is, if 80% of 300 M people live in cities of 10 M people or more, we can determine how many 10 M person cities there are; etc.)

			Here's the nested expression:

			<math>
			300 M = 3e8 people \times \left(
			\dfrac{.80 people}{1e6 people/city} + .20 \times \left(
			\dfrac{.80 people}{1e5 people/city} + .20 \times \left(
			\dfrac{.80 people}{1e4 people/city} + .20 \times \left(
			\dfrac{.80 people}{1e3 people/city} + .20 \times \left(
			\dfrac{.80 people}{1e2 people/city} + \dfrac{.20}{1e1 people/city}
			\right)
			\right)
			\right)
			\right)
			\right)
			</math>

2017-05-28T18:55:14Z

Number of hours in 1M seconds

← Older revision		Revision as of 18:55, 28 May 2017
Line 641:		Line 641:
	Do this multiple times, splitting into groups that live in cities of 10M, 1M, 100k, 10k, 1k, and <1k, we get:		Do this multiple times, splitting into groups that live in cities of 10M, 1M, 100k, 10k, 1k, and <1k, we get:

	[[Image:PopCenterTable.~~png~~\|500px]]		[[Image:PopCenterTable.jpg\|500px]]