Data Structure and Algorithms Using C++. Sachi Nandan Mohanty

       Introduction

      An important question is: How efficient is an algorithm or piece of code? Efficiency covers lots of resources, including:

      CPU (time) usage

      Memory usage

      Disk usage

      Network usage

All are important but we will mostly talk about CPU time

      Be careful to differentiate between:

      Performance: how much time/memory/disk/... is actually used when a program is running. This depends on the machine, compiler, etc., as well as the code.

      Complexity: how do the resource requirements of a program or algorithm scale, i.e., what happens as the size of the problem being solved gets larger. Complexity affects performance but not the other way around. The time required by a method is proportional to the number of “basic operations” that it performs. Here are some examples of basic operations:

      one arithmetic operation (e.g., +, *). one assignment one test (e.g., x == 0) one read one write (of a primitive type)

       Note: As an example,

      O(1) refers to constant time.

      O(n) indicates linear time;

      O(n^k) (k fixed) refers to polynomial time;

      O(log n) is called logarithmic time;

      O(2ⁿ) refers to exponential time, etc.

       n2 + 3n + 4 is O(n2), since n2 + 3n + 4 < 2n2 for all n > 10. Strictly speaking, 3n + 4 is O(n2), too, but big-O notation is often misused to mean equal to rather than less than.

1.7 How to Determine Complexities

      In general, how can you determine the running time of a piece of code? The answer is that it depends on what kinds of statements are used.

       1. Sequence of statements

       statement 1; statement 2; ... statement k;

Note: this is code that really is exactly k statements; this is not an unrolled loop like the N calls to addBefore shown above.) The total time is found by adding the times for all statements:

      total time = time(statement 1) + time (statement 2) + ... + time(statement k)

      If each statement is “simple” (only involves basic operations) then the time for each statement is constant and the total time is also constant: O(1). In the following examples, assume the statements are simple unless noted otherwise.

       2. if-then-else statements

       if (cond) { sequence of statements 1 } else { sequence of statements 2 }

      Here, either sequence 1 will execute, or sequence 2 will execute. Therefore, the worst-case time is the slowest of the two possibilities: max(time(sequence 1), time(sequence 2)). For example, if sequence 1 is O(N) and sequence 2 is O(1) the worst-case time for the whole if-then-else statement would be O(N).

       3. for loops

       for (i = 0; i < N; i++) { sequence of statements }

      The loop executes N times, so the sequence of statements also executes N times. Since we assume the statements are O(1), the total time for the for loop is N * O(1), which is O(N) overall.

       4. Nested loops

       for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { sequence of statements } }

The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M). In a common special case where the stopping condition of the inner loop is j < N instead of j < M (i.e., the inner loop also executes N times), the total complexity for the two loops is O(N²).

       5. Statements with method calls:

      When a statement involves a method call, the complexity of the statement includes the complexity of the method call. Assume that you know that method f takes constant time, and that method g takes time proportional to (linear in) the value of its parameter k. Then the statements below have the time complexities indicated.

       f(k); // O(1) g(k); // O(k)

      When a loop is involved, the same rule applies. For example:

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

      has complexity (N²). The loop executes N times and each method call g(N) is complexity O(N).

       Examples

       Q1. What is the worst-case complexity of the each of the following code fragments?

      Two loops in a row:

       for (i = 0; i < N; i++) { sequence of statements } for (j = 0; j < M; j++) { sequence of statements }

      Answer: The first loop is O(N) and the second loop is O(M). Since you do not know which is bigger, you say this is O(N+M). This can also be written as O(max(N,M)). In the case where the second loop goes to N instead of M the complexity is O(N). You can see this from either expression above. O(N+M) becomes O(2N) and when you drop the constant it is O(N). O(max(N,M)) becomes O(max(N,N)) which is O(N).

       Q2. How would the complexity change if the second loop went to N instead of M?

      A nested loop followed by a non-nested loop:

       for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { sequence of statements } } for (k = 0; k < N; k++) { sequence of statements }

      Answer: The first set of nested loops is O(N²) and the second loop is O(N). This is O(max(N²,N)) which is O(N²).

       Q3. A nested loop in which the number of times the inner loop executes depends on the value of the outer loop index:

       for (i = 0; i < N; i++) { for (j = i; j < N; j++) { sequence of statements } }

      Answer: When i is 0 the inner loop executes N times. When i is 1 the inner loop executes N-1 times. In the last iteration of the outer loop when i is N-1 the inner loop executes 1 time. The number of times the inner loop statements execute is N + N-1 + ... + 2 + 1. This sum is N(N+1)/2 and gives O(N²).

       Q4. For each of the following loops with a method call, determine the overall complexity. As above, assume that method f takes constant time, and that method g takes time linear in the value of its parameter.

      a. for (j = 0; j < N; j++) f(j); b. for (j = 0; j < N; j++) g(j); c. for (j = 0; j < N; j++) g(k);

      Answer: a. Each call to f(j) is O(1). The loop executes N times so it is N x O(1) or O(N).

      b. The first time the loop executes j is 0 and g(0) takes “no operations.” The next time j is 1 and g(1) takes 1 operations. The last time the loop executes j is N-1 and g(N-1) takes N-1 operations. The total work is the sum of the first N-1 numbers and is O(N²).

c. Each time through the loop g(k) takes k operations and the loop executes N times. Since you do not know the relative size of k and N, the overall complexity is O(N x k).

1.8 Questions

      1 What