Algorithms/Recursion Analysis - Revision history

Admin: Fix math syntax: collapsed block math to inline and removed space between 2 and (; also fixed typos (pinted→printed, numberof→number of, llength→length, +1→-1 in code) (via update-page on MediaWiki MCP Server)

2026-06-06T00:02:45Z

Fix math syntax: collapsed block math to inline and removed space between 2 and (; also fixed typos (pinted→printed, numberof→number of, llength→length, +1→-1 in code) (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 00:02, 6 June 2026
Line 44:		Line 44:
	draw interval(center length - 1) /* recursively draw top ticks */		draw interval(center length - 1) /* recursively draw top ticks */
	draw line(center length) /* draw center tick */		draw line(center length) /* draw center tick */
	draw interval(center length +1) /* recursively draw bottom ticks */		draw interval(center length - 1) /* recursively draw bottom ticks */

	function draw ruler(number of inches, major length):		function draw ruler(number of inches, major length):
	draw line(major ~~llength~~, '0') /* 0 inch line */		draw line(major length, '0') /* 0 inch line */
	for j in range(1, 1+inches+1):		for j in range(1, 1+inches+1):
	draw interval(major length - 1) /* draw interior ticks for inch */		draw interval(major length - 1) /* draw interior ticks for inch */
Line 68:		Line 68:
	'''Justification:''' (Proof by induction) We note first the base case is c = 0, which generates no output, and <math>2^0 - 1 = 1 - 1 = 0</math>. This is the base of the claim.		'''Justification:''' (Proof by induction) We note first the base case is c = 0, which generates no output, and <math>2^0 - 1 = 1 - 1 = 0</math>. This is the base of the claim.

	Next, we can see that the number of lines printed by draw_interval(c) is one more than twice the number generated by a call to draw_interval(c-1), as ~~once~~ center line is ~~pinted~~ between two such recursive calls. By induction, the ~~numberof~~ lines must be 1 + 2 * prior number, which is:		Next, we can see that the number of lines printed by draw_interval(c) is one more than twice the number generated by a call to draw_interval(c-1), as one center line is printed between two such recursive calls. By induction, the number of lines must be 1 + 2 * prior number, which is:

	<math>		<math>1 + 2(2^{c-1} - 1) = 1 + 2^c - 2 = 2^c - 1</math>
	1 + 2 (2^{c-1} - 1) = 1 + 2^c - 2 = 2^c - 1
	</math>

	Therefore it is proven.		Therefore it is proven.

Admin at 00:22, 12 July 2017

2017-07-12T00:22:12Z

← Older revision		Revision as of 00:22, 12 July 2017
Line 77:		Line 77:

	This relates to the [[Algorithms/Recurrence Relation]] concept.		This relates to the [[Algorithms/Recurrence Relation]] concept.






			{{AlgorithmsFlag}}

Admin: Created page with "=Notes= This page contains notes on algorithmic analysis of recursive functions. ==Goodrich Chapter 4== ===English Ruler Example: Setup=== An English ruler is a ruler in w..."

2017-07-12T00:21:39Z

Created page with "=Notes= This page contains notes on algorithmic analysis of recursive functions. ==Goodrich Chapter 4== ===English Ruler Example: Setup=== An English ruler is a ruler in w..."

New page

=Notes=

This page contains notes on algorithmic analysis of recursive functions.

==Goodrich Chapter 4==

===English Ruler Example: Setup===

An English ruler is a ruler in which each major unit has major tick marks, and minor units have minor tick marks occurring at successive halves. Between marks for whole inches, there are minor ticks at 1/2 inch intervals; between the 1/2 inch intervals, minor ticks at 1/4 inch intervals; etc.

To draw in ascii:

<pre>
---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2
</pre>

Implementation looks like this:

<pre>
function draw line(tick length, tick label):
line = '-' (tick length times)
if tick label:
line += ' ' + tick label
print line

function draw interval(center length):
if center length > 0:
draw interval(center length - 1) /* recursively draw top ticks */
draw line(center length) /* draw center tick */
draw interval(center length +1) /* recursively draw bottom ticks */

function draw ruler(number of inches, major length):
draw line(major llength, '0') /* 0 inch line */
for j in range(1, 1+inches+1):
draw interval(major length - 1) /* draw interior ticks for inch */
draw line(major length, str(j)) /* draw inch j line and label */
</pre>

in general, an interval with tick length L >= 1 is composed of the following:
* an interval with a central tick length L-1
* a single tick of length L
* an interval with a central tick length L-1

===English Ruler Example: Analysis===

Fundamental question we want to know, in analyzing the above method, is how many lines of output it will produce by a call to draw_interval(c), where c is a center length.

Each line of output is based upon a call to the draw line utility, and each recursive call to draw interval makes exactly one call to draw line, unless 0.

'''Proposition:''' For <math>c \geq 0</math>, a call to <code>draw_interval(c)</code> results in precisely <math>2^c - 1</math> lines of output.

'''Justification:''' (Proof by induction) We note first the base case is c = 0, which generates no output, and <math>2^0 - 1 = 1 - 1 = 0</math>. This is the base of the claim.

Next, we can see that the number of lines printed by draw_interval(c) is one more than twice the number generated by a call to draw_interval(c-1), as once center line is pinted between two such recursive calls. By induction, the numberof lines must be 1 + 2 * prior number, which is:

<math>
1 + 2 (2^{c-1} - 1) = 1 + 2^c - 2 = 2^c - 1
</math>

Therefore it is proven.

This relates to the [[Algorithms/Recurrence Relation]] concept.