Class 26 - Complexity and Subclassing
I've made some updates to the provided code for Project 5. You can see all the changes in bitbucket: https://bitbucket.org/cs1120/project5/commits/506eea0e7d6929e374fa2a3d00d45d8c5b114530.
You can syncronize your forked repository with these changes by following these directions in SourceTree:
Repository | Repository Settingsfrom the menu.
You should see the
Remotespane, which will have one repository in it now. Click
Addto add a new remote.
Give it a name (like
upstream). For the URL, enter
Okto finish adding the remote repository.
Pullin the main window, and for the repository in
Pull from repositoryselect
upstream(the name you used in step 3).
This should update your version to match the provided code. If there are any changes that cannot be automatically merged with your version, there will be conflicts that you will need to resolve by manually editing the conflicting files (this shouldn't happend, unless you modified the provided code files that have been updated).
The complexity of a problem is a short way of saying "the runtime cost of the least expensive algorithm possible solving the problem for the most expensive input of a given size".
For most problems, it is very difficult to get a tight (Θ) bound on the complexity of the problem since this requires reasoning about the best possible algorithm. Sorting is a rare exception where we know the complexity is in Ω(N log N) and know of algorithms that solve the sorting problem with average-case running time in Θ(N log N), so can say the complexity of the problem is in Θ(N log N) where N is the number of elements in the input.
Even for (seemingly) simple problems like multiplcation, we do not yet know a tight bound on the complexity of the problem.