CSC 216 Lecture Notes - Lecture 16: Time Complexity, Dynamic Array, Linked List
CSC216: Programming Concepts – Java
Class 16: Stacks
October 18th, 2016
Program Complexity
• Abstract Data Types (ADTs): A specification of a collection or data and the operations
that can be performed on it
o Describes what a collection does, not how the collection does it
o As a liet, e do’t eed to ko the iteral orkigs of the ADT
▪ We just need to understand the idea of the collection and what
operations it can perform
o Understanding the runtime efficiency is also important for choosing a collection
• Lists are linear data structures
o The hae stadard operatios, like get, set, reoe, add…
o A client uses the abstraction of the list without needing to know the details
about the internal workings (most of the time, at least)
• The reason that there are multiple kinds of lists is because either kind (ArrayList and
LinkedList hae arious tradeoffs…
o They differ in how the data is stored internally and how the operations are
implemented
o You can implement a data structure to meet an interface
▪ Client code then uses the interface
▪ And then, implementation can be customized for the characteristics of
your data
• Whe osiderig opleit…
o Make sure to note the Big-Oh notation (detailed in the second section of these
notes)
▪ The growth rate is asymptotically less than or equal to the given growth
rate
o There are operations that may be more efficient
▪ Adding/removing to/from the end of an array list is O(1)
▪ Adding/removing to/from the front of a linked list is O(1)
▪ Adding additionally references to a linked list can increase efficiency
o We can create specialized data structures that take advantages of these
efficiencies
Runtime Efficiency
• Efficiency: A measure of the use of computing resources
o Can be relative to speed (time), memory (space), etcetera
• When considering runtime efficiency, assume the following:
find more resources at oneclass.com
find more resources at oneclass.com
o Any single Java statement takes the same amount of time to run
o A ethod all’s rutie is easured the total of the stateets iside the
ethod’s od
o A loop’s rutie, if the loop repeats N ties, is N times the runtime of the
statements in its body
•
• Algorithm Growth Rates
o We measure runtime in proportion to the input data size, N.
▪ Growth Rate: Change in runtime as N changes
o Say an algorithm runs 0.4N3 + 25N2 + 8N + 17 statements
▪ Consider the runtime when N is extremely large
▪ We ignore constants like 25 because they are tiny next to N
▪ The highest-order term (N3) dominates the overall runtime
o We sa that this algorith rus o the order of N3
▪ Or O(N3 for short Big-Oh of N ued
• Complexity Class: A categor of algorith effiie ased o the algorith’s
relationship to the input size N
find more resources at oneclass.com
find more resources at oneclass.com
