Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
Update knuth-optimization.md#1438
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
In time complexity proof cancellation explanation, j=N -> j=N-1
This is technically true probably should say something showing how when j=N-1 the second argument is N to be more thorough. |
FloppaInspector commentedApr 12, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Well, it should be clear that since the term j=N-1 remains, and i iterates range [1, N], opt(k, N) form should make clear sense. Saying j=N is a lot more confusing, since the positive term is "opt(i+1, j+1)", not "opt(i, j)", where j=N makes sense, but it isn't the positive term and people can easily misinterpret for the negative term. Though I don't think more explanation is needed, since positive term should clearly refer to "opt(i+1, j+1)" where j=N-1 is correct. Plus j cannot be N because j iterates range [i, N-1]. |
mhayter commentedApr 12, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
You're right. I guess I'd prefer to add an additional line but surely it's not more wrong than what's already there. |
862a10b
intocp-algorithms:mainUh oh!
There was an error while loading.Please reload this page.
In time complexity proof cancellation explanation, j=N -> j=N-1