# Standard Analysis Techniques

**Standard Analysis Techniques**

- Constant time statements
- Analyzing Loops
- Analyzing Nested Loops
- Analyzing Sequence of Statements
- Analyzing Conditional Statements

**Constant time statements**

- Simplest case: O(1) time statements
- Assignment statements of simple data types

int x = y; - Arithmetic operations:

x = 5 * y + 4 – z; - Array referencing:

A[j] = 5; - Array assignment:

” j, A[j] = 5; - Most conditional tests:

if (x < 12) …

**Analyzing**** Loops[1]**

- Any loop has two parts:
- How many iterations are performed?
- How many steps per iteration?

** ****int**** sum = 0,j;**

** for (j=0; j < N; ****j++****)**

** sum = sum +j;**

- Loop executes N times (0..N-1)
- 4 = O(1) steps per iteration
- Total time is N * O(1) = O(N*1) = O(N)

**Analyzing Loops[2]**

- What about this
**for**loop?

** ****int**** sum =0, j;**

** for (j=0; j < 100; ****j++****)**

** sum = sum +j;**

- Loop executes 100 times
- 4 = O(1) steps per iteration
- Total time is 100 * O(1) = O(100 * 1) = O(100) = O(1)

**Analyzing**** Nested Loops[1]**

- Treat just like a single loop and evaluate each level of nesting as needed:

**int** **j,k****;**

** for (j=0; j<N; ****j++****)**

** for (k=N; k>0; k–)**

** sum += ****k+j****;**

- Start with outer loop:
- How many iterations? N
- How much time per iteration? Need to evaluate inner loop
- Inner loop uses O(N) time
- Total time is N * O(N) = O(N*N) = O(N2)

**Analyzing**** Nested Loops[2]**

- What if the number of iterations of one loop depends on the counter of the other?

** ****int** **j,k****;**

** for (j=0; j < N; j++)**

** for (k=0; k < j; k++)**

** sum += ****k+j****;**

- Analyze inner and outer loop together:
- Number of iterations of the inner loop is:
- 0 + 1 + 2 + … + (N-1) = O(N2)

**Analyzing**** Sequence of Statements**

- For a sequence of statements, compute their complexity functions individually and add them up

** **for (j=0; j < N; j++)

for (k =0; k < j; k++)

sum = sum + j*k; O(N2)

for (l=0; l < N; l++)

sum = sum -l; O(N)

cout<<“Sum=”<<sum; O(1)

Total cost is O(N2) + O(N) +O(1) = O(N2)

SUM RULE

**Analyzing**** Conditional Statements**

What about conditional statements such as

** if (condition) **

** statement1;**

** else**

** statement2;**

where statement1 runs in O(N) time and statement2 runs in O(N2) time?

We use “worst case” complexity: among all inputs of size N, that is the maximum running time?

The analysis for the example above is O(N2)

**Best Case**

- Best case is defined as which input of size
*n*is cheapest among all inputs of size*n*. - “The best case for my algorithm is
*n*=1 because that is the fastest.” WRONG!