Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithm Analysis - Coggle Diagram
Algorithm
Analysis
Justification
Tecniques
By Example
counterexample
The "Contra" Attack
contrapositive
De Morgan's Law
contradiction
Induction
Loop invariants
Definitions
Algorithm
step-by-step procedure for performing
some task in a finite amount of time
Data Structure
systematic way of organizing
and accessing data
Running Time
a natural measure of "goodness"
Depends On
input content
hardware environment
input size
becomes an argument for
measuring running time
software environment
Approaches
To Measurement
Experimental
Studies
"wall clock"
measuring running time
in seconds
Python function
time.time()
CPU cycles
Python function
time.clock()
Series Of
Measurement
Python module
timeit
Challenges
hard to compare results
obtained in different environments
measurements could be done
on limited set of inputs
algorithm should be fully implemented
to start measurements
Asymptotic
Analysis
Solves Exp. Analysis
Challenges
allows to describe algorithm
using pseudo language
covers all possible inputs
hardware and
software independent
Method
treats primitive operations
as taking a constant time
calculates order of growth
for algorithm running time
takes worst time for each
set of input of size n
disregards
constant factors
Big-Oh
given functions mapping
positive integers
to positive real numbers
f(n) is O(g(n))
f(n) is Big-Oh of g(n)
f of n is Big-Oh of g of n
if there is such c > 0 and n >= 1
that f(n) <= cg(n) for n >= n.
the function \( 8n + 5 \; is \; O(n) \)
allows to ignore constant factors
and lower-order terms
\( 5n^{4} + 3n^{3} + 2n^{2} + 4n + 1 \; is \; O(n) \)
the highest-degree term in a polynomial
is the term that determines the
asymptotic growth rate of that polynomial
\( n^{2} \)
Big-Omega
an opposite to Big-Oh
if f(n) is O(g(n))
then g(n) is Big-Omega of f(n)
Big-Theta
binds Big-Oh and Big-Omega together
if
f(n) is Big-Oh of g(n) and
f(n) is Big-Omega of g(n) then
f(n) is Big-Theta of g(n)