Computational Complexity Flashcards
What is computational complexity
determines if an algorithm is feasible for a certain problem, as data size increases and allows comparison between two algorithms being used for the same problem
time efficiency
how run time changes as the problem’s parameters and input increases in size
what does n represent
the problem size (length of list/array)
what does T(n) represent
amount of time it takes to execute problem size n
the equation represents if the algorithm is constant, linear, quadratic, exponential
this tells how time is proportional to the size of the list
how do you get the equation for T(n)
by counting the # of operations an algorithm will need for problem size N
cannot get the exact formula, just general characteristics
what is Big-O notation
mathematical notation for talking about general categories of notations
the characteristics of Big-O notation tell us whether the formula is quadratic, linear etc
O(1), O(n) etc
How to get Big-O formula
from T(n), get the most dominate term and drop coefficient
General rules
Rule 1 - straight-line code
Rule 2 - consecutive sections of code
Rule 3 - if statements
Rule 4 - simple loops
Rule 1 - straight line code
- straight-line code has no function calls, not dependent on the size of the input
- constant-time operations O(1)
EX. variable assignment, arithmetic, array access
Rule 2 - consecutive sections of code
- where 1 bit of code runs, followed by a loop or another piece of code
- to get Big-O, find max O(n) of O(f(n) and O(g(n))
Rule 3 - if statements
- find max of if and else statement
EX. max(f(n) and g(n))
nested loops require finding the complexity of inner loop * outer loop
rule 4 - simple loops
The complexity of the loop body TIMES the number of iterations
EX. 2n*O(n^2) = O(n^3)
** repeating a constant number of times in a loop doesn’t change complexity **
** nested loops require the complexity of inner loop * complexity of outer loop **
O(log n)
- decreasing iterations through the array consistently
EX. n = n/2
most efficient
Attributes of algorithms
- solves computational problem
- ease of understanding
- efficiency
- elegance
Comparing algorithms
- comparing attributes
- comparing time complexity best/worst/avg cases
Best, worst, average complexity
Best - smallest amount (T(n) = 1)
Worst - greatest amount of work (T(n) = n)
Avg - likelihood of different scenarios occurring (T(n) = n/2)
O(1)
constant time
- arithmetic, variable assignments, accessing an array
O(n)
linear time
- proportional to the size of the list/array
O(n^2)
quadratic
- nested loops, dependent on the size of the list/array
O(log n)
- dividing the proportion of the array accessed each time
- efficient
- the base is what n size is divided by
EX. O(log 2 n) O(log 3 n)
O(2^n)
- grows fastest
- polynomial
