CSC148H1 Lecture Notes - Lecture 29: Time Complexity, Call Stack
CSC148: Lecture 29: Big-Oh and Memory Model
References: Code seen in the pictures can be found on the CSC148 website:
http://www.teach.cs.toronto.edu/~csc148h/winter/
Trade-Offs
- Speed vs. accuracy
o E.g. smart player vs. finding the optimal solution
- Time vs. space
- Time vs. time
o E.g. Sorted lists require slower insert and delete than unsorted lists, but have
faster search
o E.g. Balanced search trees require slower insert and delete than regular search
trees but have faster search
Common Pitfalls for Big-Oh Questions
- Don’t assume every loop runs in linear time
o E.g. 2 nested loops don’t necessarily mean quadratic run time
- Don’t assume every line of code runs in constant time
o Helper functions often take time, which depends on size of input
o Need to take into account their running time to fully analyze the original function
- Don’t assume running time is based on the data structure
o Just because you know what the input data structure is doesn’t mean you can
ignore the rest of the code
- Don’t just count the number of recursive calls
o Counting the number of recursive calls is important but not the only thing that
matters
o Also look at non-recursive steps the function takes
▪ Watch out for ones that don’t run in constant time
- Define all variables used in Big-Oh expressions
o Otherwise, you don’t know what you’re talking about
- The “best case” is NOT when the input is empty
o Best and worst cases describe families of inputs
▪ Include inputs of all input size
- Don’t assume that the running time depends on “the most important input”
o Functions often take more than 1 input and the running time depends on the
sizes of more than just 1 input
o Take into account all possible combinations of input sizes for all the inputs
Memory Model
- Call stack- created for:
o Function calls
o Nested functions calls
o Recursive function calls
- Heap
o Created for all objects
o Protected for each function execution “environment”
Tracing Call Stack
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
References: code seen in the pictures can be found on the csc148 website: http://www. teach. cs. toronto. edu/~csc148h/winter/ Speed vs. accuracy: e. g. smart player vs. finding the optimal solution. Sorted lists require slower insert and delete than unsorted lists, but have faster search: e. g. Balanced search trees require slower insert and delete than regular search trees but have faster search. Don"t assume every loop runs in linear time: e. g. 2 nested loops don"t necessarily mean quadratic run time. Don"t assume every line of code runs in constant time: helper functions often take time, which depends on size of input, need to take into account their running time to fully analyze the original function. Don"t assume running time is based on the data structure: just because you know what the input data structure is doesn"t mean you can ignore the rest of the code. Define all variables used in big-oh expressions: otherwise, you don"t know what you"re talking about.
