Commite24c674

authored

Update knuth-optimization.md

In time complexity proof cancellation explanation, j=N -> j=N-1

1 parent82a06ff commite24c674Copy full SHA for e24c674

File tree

-1

lines changed

-1

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -77,7 +77,7 @@ $$`
`77`	`77`	`\sum\limits_{i=1}^N \sum\limits_{j=i}^{N-1} [opt(i+1,j+1)-opt(i,j)].`
`78`	`78`	`$$`
`79`	`79`
`80`		`-As you see, most of the terms in this expression cancel each other out, except for positive terms with $j=N$ and negative terms with $i=1$. Thus, the whole sum can be estimated as`
	`80`	`+As you see, most of the terms in this expression cancel each other out, except for positive terms with $j=N-1$ and negative terms with $i=1$. Thus, the whole sum can be estimated as`
`81`	`81`
`82`	`82`	`$$`
`83`	`83`	`\sum\limits_{k=1}^N[opt(k,N)-opt(1,k)] = O(n^2),`

Comments

(0)