Timeline for Time complexity analysis for dynamic programming using memoization
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2022 at 18:19 | comment | added | John L. | @SiddharthaSadhukhan Please come to chat with me. | |
| May 12, 2022 at 17:55 | comment | added | Siddhartha Sadhukhan | Thank you John L., I had manged to compute the complexity O(mn) but failed to thought at this level. This one will be acting like a reference for my future analysis. One more thing, do we have any other way to dry-run a recursive solution except recursion tree. And thank you once again | |
| May 12, 2022 at 17:12 | comment | added | John L. | @SiddharthaSadhukhan Does my updated answer explain that expression clearly? | |
| May 12, 2022 at 17:09 | history | edited | John L. | CC BY-SA 4.0 |
More explanation per feedback.
|
| May 12, 2022 at 15:56 | comment | added | Siddhartha Sadhukhan | Thank you John for the comprehensive explanation. Could you please explain "(17−7+1)(m+1)(n+1)+3(1+4(m+1)(n+1))+2" part. | |
| May 12, 2022 at 15:49 | vote | accept | Siddhartha Sadhukhan | ||
| May 12, 2022 at 8:18 | comment | added | John L. | For a detailed introduction to dynamic programming and time-complexity analysis of it, check chapter "Dynamic Programming", Introduction to Algorithms by CLRS, where you can find many well-explained examples. | |
| May 12, 2022 at 5:24 | history | edited | John L. | CC BY-SA 4.0 |
Stated the general principle.
|
| May 11, 2022 at 22:03 | comment | added | John L. |
The total number of line-executions in the answer predicts that your algorithm will run well within 1 second even if s.length =300 and p.length <= 300.
|
|
| May 11, 2022 at 22:01 | history | edited | John L. | CC BY-SA 4.0 |
Fixed typos
|
| May 11, 2022 at 21:50 | history | answered | John L. | CC BY-SA 4.0 |