Class 26  Complexity and Subclassing
Syncing Repositories
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:

Select
Repository  Repository Settings
from the menu. 
You should see the
Remotes
pane, which will have one repository in it now. ClickAdd
to add a new remote. 
Give it a name (like
upstream
). For the URL, enterhttps://bitbucket.org/cs1120/project5
. ClickOk
to finish adding the remote repository. 
Click
Pull
in the main window, and for the repository inPull from repository
selectupstream
(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).
Slides
Problems
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 averagecase 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.