2. Algorithm Analysis

2.1. Algorithm Analysis

For each of the following six programs:

1. Give an analysis of the running time (Big-Oh).

2. Implement and give the running time for several values of \(N\).

3. Compare your analysis with the actual running time (plot the results).

alg 1

sum = 0;
for (i = 0; i < n; i++){
    sum++;
}

alg 2

sum = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < n; j++){
        sum++;
    }
}

alg 3

sum = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < n * n; j++){
        sum++;
    }
}

alg 4

sum = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < i; j++){
        sum++;
    }
}

alg 5

sum = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < i*i; j++){
        for (k = 0; k < j; k++){
            sum++;
        }
    }
}

alg 6

sum = 0;
for (i = 0; i < n; i++){
    for (j = 0; j < i*i; j++){
        if (j % i == 0){
            for (k = 0; k < j; k++){
                sum++;
            }
        }
    }
}

2.2. LeetCode

If you are done you can start doing the following problems on LeetCode:

• https://leetcode.com/problems/min-stack/

• https://leetcode.com/problems/range-sum-query-immutable/

• https://leetcode.com/problems/binary-search-tree-iterator/