Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structure (Chapter 3) - Coggle Diagram
Data Structure (Chapter 3)
measure the efficiency of algorithm
Theoretical analysis
Empirical analysis
Empirical analysis
algorithm that uses less resources is the best.
Measure the recourses (time) used
based on time elapsed = final-start
Challenges:
e implementation of one algorithm is better than
the other.
they should be executed on the
same software/hardware environments.
Algorithms must be implemented in order to execute them and calculate time experimentally
The test data might unfairly favor one algorithm.
Theoretical analysis
Features
Takes into account all possible inputs
Allows us to evaluate the speed of an algorithm independent of the
hardware/software environment
Uses a high-level description of the algorithm instead of an implementation
Counting Primitive Operations
Primitive operations
• Following an object reference
Performing an arithmetic operation
Assigning a value to a variable
Comparing two numbers
Accessing a single element of an array by index
Calling a method
returning from a method
Big-Oh notation
Common Asymptotic Functions
linear O(n)
Growth is directly proportional to n.
logarithmic O(log n)
Growth increases slowly comparing to n.
n log n O(n log n)
sorting using divide and conquer
quadratic O((n^2)
typical in two nested loops
constant O(1)
Growth is independent of the size of input data
cubic O(n^3)
typical in three nested loops
exponential O(2^n)
it growths extremely and possibly impractical
o describe time complexity which
means amount of time to run an algorithm.
defines an
upper bound
of an algorithm (worst case)
Asymptotic analysis
evaluate the performance of an algorithm in terms
of input size
algorithm growth rate as the input
size becomes very large.
The growth rate is not affected by :
Lower order term
Constant factor
determines the running time in big-Oh notation