Building a summation from analyzing code?

Question

I have a midterm tomorrow, and we are supposed to be able to analyze code. This is honestly the only thing that I don't understand at all. Basically we are given something like this:

Consider this Java method for comparing two strings. This method has two inputs and so we should use two variables to express the running time. Let n be the length of a and let m be the length of b. We can express the running time as a function of n and/or m. It will help if we assume without loss of generality that n < m.

  private static int compareStrings ( String a , String b) {
       int i = 0; 
       while ( i < a . length () && i < b. length ( ) ) { 
           if (a . charAt ( i ) < b. charAt ( i ) ) return −1;

           if (a . charAt ( i ) > b. charAt ( i ) ) return 1;

           i ++;
       }
       if (a . length () < b. length ( ) ) return −1; 
       if (a . length () > b. length ( ) ) return 1; 
 }

a) Express the worst case running time of this method as a sum.

b) Simplify this sum and state its big-oh bound.

the notation I need it in is :

n
Σ i
i= 1

I don't understand how to build a sum out of this code, or get it's running time. Step by step instructions would be great. This problem given was a practice problem and not homework. I really want to understand this!!!

Answer 1

Ok, first of all the code is buggy. It has a Unicode character instead of a minus sign and it doesn't return anything if none of the conditions match. This won't work as method has to return an integer.

Following is the fixed method.

private static int compareStrings ( String a , String b) {
       int i = 0; 
       while ( i < a . length () && i < b. length ( ) ) {
           if (a . charAt ( i ) < b. charAt ( i ) ) {
               return -1;
           }

           if (a . charAt ( i ) > b. charAt ( i ) ) {
               return 1;
           }

           i ++;
       }
       if (a . length () < b. length ( ) ) {
           return -1; 
       }
       if (a . length () > b. length ( ) ) {
           return 1;
       }

       return 0;
 }

Now lets start breaking it down to calculate the complexity.

First complexity as sum

To do this we have to count the number of operations done by this method. Lets say that a stand alone operation takes 1 unit of execution time.

There are 5 types of different independent operations in this method.

1. Declaration of a variable
2. Look up of length of string
3. Condition evaluation (Logical condition)
4. Logical expression evaluation of 2 boolean values
5. Returning a value from the method.

Assuming that all the above stand alone operations take 1 unit of time we can go ahead and calculate the total time taken by the method.

int i = 0;
//time taken 1 unit.

while ( i < a . length () && i < b. length ( ) )
//time taken 5n + 2 unit

loop statement consists of 5 operations

1. 2 length lookups for a and b
2. 2 length comparisons with i
3. 1 comparison of the output of length comparison ( && operation)

Since we are considering the worst case loop would have to run n times. Since loop runs at max n times as n is less than m and loop breaks whenever i is less than n. So this gives us 5n unit of time

However would be one more check for i when it's value is incremented to n when the loop will break as i < a.length() <=> i < n will result in false. Here only first 2 operations will be evaluated as the second operation will be short circuited.

1. a.length() //1 unit of time
2. i < a.length() //1 unit of time

That gives us 5n+2 unit of time for while statement.

Next two statements are almost identical if statements. Since we are considering the worst case neither of the two will result in true otherwise loop would break.

if (a . charAt ( i ) < b. charAt ( i ) ) {
   return -1;
}
//3n unit of time

if (a . charAt ( i ) > b. charAt ( i ) ) {
   return 1;
}
//3n unit of time

Both of these statements get executed n times. Each consists of 3 stand alone operations (2 charAt(i) lookups and 1 condition evaluation).

So total time taken by both of these statements will be 6n unit of time.

Next is

i++;
//n unit of time

This is simple as loop runs n times and it is stand alone operation.

Finally next and last statement is

if (a . length () < b. length ( ) ) {
   return -1; 
}
//4 units of time

It has 4 operations (2 length lookups, 1 condition, and 1 return statement)

Now no more statements will be executed as we know for a fact that n < m

Total sum of execution time will be as following.

sum = 1 + (5n+2) + (6n) + n + 4
    = 12n + 7
sum = 12n + 7

Now this is still not the worst case, as n has an upper bound that's m

We have to maximize n in order to make the worst case possible. Maximum value that n can assume is m-1 as n < m (strictly less than)

so in the worst case

n = m - 1

replacing that in the sum expression 12n + 7

sum = 12n + 7
    = 12(m-1) + 7
    = 12m - 5
sum = 12m - 5

This is our answer of first part

worst case running time of the method as sum

12m - 5

Now since Big-O bound for this function would be O(m)

As following is the definition of Big-O

f(x) is bounded by g(x)

if and only if for some sufficiently large constant x₀ for which there exists an M for which below is true.

Here

f(m) = 12m -5
g(m) = m

m0 = 5/12
M = 12

so O(g(x) = O(m) is the upper bound for the sum.

Simplified sum in big-oh bound is

O(m)

Answer 2

Looking at the code, it creates an iterator (i), then iterates through until it reaches the end of one of the strings (the shorter, obviously, represented by length n).

Since there's only one loop, and that loop only iterates through n times, the "running time" of the algorithm could probably be described as counting the "if" statements that would result, or "2n+2". In Big-O notation, that comes out to O(n). The extra two if checks at the end are constant, so not used in the computation.

Hmm, the sum you're looking for would seem to be:

n
Σ k
i = 1

Read this as "for each value from 1 to n of i, add k to the total", which should result in k*n (and a resulting big-O of O(n)). I use k here because I don't know the cost of the inner loop, but it should be constant. If you feel your class would use 1 for "one time through the body of the loop", then that's fine too.

Answer 3

The worst case run time is O(n).

Why?
1. Because we assume that n < m and this algorithm only compares characters as long as there are characters remaining in both strings [characters yet to be compared].

Naturally this condition fails to hold when there are no more characters in the shortest string, a.

2. Because the worst case must occur when the while loop is not interrupted by a return.

This can coincide with case in which we evaluate n times.

The only stipulation is that a be a substring of b such that a[0] == b[0] also.

Cost is the sum of

• evaluating the while condition
• the cost of the two comparisons, etc. in the body of the loop
• incrementing i

It is bounded above by nc + k where c is the worst case cost of the while loop body, k is the cost of the operations only evaluated once (such as the return statement), and n has the previously agreed-upon significance.

If you allow n to rise without bound you can see that this fits the definition of O(n).