StateAnalysis.md (1409B)
1 # State Analysis 2 3 Ch 3 4 5 **Definition:** State analysis, in the context of algorithms, is a strategy for computing the time complexity of an algorithm that analyzes the current state of the algorithm instead of describing each line of code and their associated complexity which becomes unruly as algorithms become more complex. 6 7 ### Steps 8 9 1. Choose a variable that captures as much state as possible (state variable) 10 2. Find an upper bound for the domain of the variable 11 3. Find upper bound for number of instructions at each state value 12 4. Multiply results from steps 2 and 3 to find total complexity (worst case complexity) 13 14 ### Example (bubble sort) 15 16 1. State variables are i and j 17 2. Upper bound for i is n+1 upper bound for j is also n thus n(n+1) 18 3. 11 total statements thus 11 is worst case number of statements per iteration (this is based on implementation, assignment, etc.) 19 4. At most 11n(n+1) = 11n^2 + 11n time complexity 20 21 As can be seen above, this is not entirely accurate to what we would find by evaluating each line of code, but this is generally close enough and only off by some constant factor. 22 23 One limit of this is when n=0 we find the above algorithm also performs 0 instructions. This is because we don't take into account the initial overhead of assignments and such as we only care about the bulk of the complexity that comes from the iteration/computation part of the algorithm.