Analysis of Algorithms Flashcards
A set of steps to accomplish a task
Algorithm
2 things we want from a computer algorithm
Correctness
Efficient Resource Usage (CPU, Memory)
The theoretical study of computer-program performance and resource usage.
Analysis of Algorithms
An algorithm that gives a correct solution but takes a long time might
be of little to no value.
Time Complexity
Algorithms can be analyzed base on ________ and _________ complexities
Time and Space
_____________ is the primary measure of efficiency.
Time
Factors that can affect runtime
speed of the computer
programming language
compiler/interpreter
other programs running
2 Types of Run Time Analysis
Empirical and Theoretical Analysis
Implement the algorithm, then run with a timer.
Empirical Analysis
We determine how long the algorithm takes as a function of the
size of its input: T(n).
Theoretical Analysis
We focus on how fast the function that
characterizes the running time _______ with the input size.
grows
We focus on how fast the function that characterizes the running time grows with the input size.
Theoretical Analysis
Upper Bound
O-notation (Big O)
is used to describe the upper bound or the maximum possible running time of the algorithm.
The O- notation
O(g(n)) is a set of functions f(n) such
that there exists positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
the upper bound is a __________________
guarantee
The running time of an algorithm on a particular input is the number of _______________ or _______ executed.
primitive operations or steps
Running time of loops:
At most the running time of the statements inside the loop times the
number of _________.
iterations
Running time for consecutive statements
Get the maximum
Running time for conditional statements
The running time of the test + the running time of the two branches.
is the minimum number of times a piece of code is executed.
best-case running time
is the maximum number of times a piece of code is executed.
worst-case running time
Linear Search Best and Worst Case Run time
Best: O(1) at index 0
Worst: O(n) at index n-1 or not in the list
Binary Search Best and Worst Case Run time
Best: O(1) at middle
Worst: O(log n)
An algorithm is O(log n) if it _____________________________________
(usually by 1⁄2).
cuts the problem size by a fraction
