3 ms·
How does one prove runtime complexity? I would love to know how to do this, just out of interest.
by omginternets 5y ago
How does one prove runtime complexity? I would love to know how to do this, just out of interest.
- ipnon 5y agoSkiena's algorithm book goes into some detail on proving complexity and proving optimality.
- omginternets 5y agoThank you. Are you by any chance aware of a more introductory text on the subject?
- ipnon 5y agoBelieve it or not Skiena's book is an introduction to algorithms! His lectures for the book are available on YouTube.[0] [0] https://youtube.com/playlist?list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx https://youtube.com/playlist?list=PLOtl7M3yp-DX6ic0HGT0PUX_w...
- omginternets 5y agoOh, perfect! Video lectures FTW! Thank you once again :)
- lpapez 5y agoUsually on interviews it is not actual proving in any mathematical sort of way. It's more like: "I am calling sort() in a loop so obviously this is O(n^2 * log n) complexity" and then the interviewer nods in approval and you move on to the next question.
- danielgh7 5y agoI personally like to go line by line in my solution and state the runtime of each line of code. Then I add them together, and write out the limit notation showing as N->inf and how I can cancel certain variables out. Its a little bit of overkill but I've found it helps me stand out a bit during interviews.