Software Quality

 

We want our software to be of high quality. But what does that mean? As is often the case, there are a variety of quality characteristics to consider.

 

                                                                                                                                                         

                                         

Quality Characteristics

 

Description

Correctness

The degree to which software adheres to its specific requirements.

Reliability

The frequency and criticality of software failure.

Robustness

The degree to which erroneous situations are handled gracefully.

Usability

The ease with which users can learn and execute tasks within the software.

Maintainability

The ease with which changes can be made to the software.

Reusability

The ease with which software components can be reused in the development of other software systems.

Portability

The ease with which software components can be used in multiple computer environments.

Efficiency

The degree to which the software fulfills its purpose without wasting resources.

 

 

THE EFFICENT USE OF RESOURCES

 

One of the most important resources is CPU time. The efficiency of an algorithm we use to accomplish a particular task is a major factor that determines how fast a program executes. Although we can analyze an algorithm relative to the amount of memory it uses, CPU time is usually the more interesting issue.

 

Let’s look at the issues related to algorithm analysis and the groundwork for using analysis techniques with an example: washing dishes by hand. If we assume that washing a dish takes 30 seconds and drying a dish takes an additional 30 seconds, then we can see quite easily that it would take a minute to wash and dry n dishes. This computation could be expressed as follows:

 

            Time (n dishes) = n  ( 30 seconds wash time + 30 seconds dry time )

                                      = 60n seconds

 

On the other hand, suppose we were careless while washing the dishes and splashed too much water around. Suppose each time we washed a dish, we had to dry not only that dish but also all of the dishes we had washed before that one. It would still take 30 seconds to wash each dish, but now it would take 30 seconds to dry the last dish (once), 230 or 60 seconds to dry the second-to-last dish (twice), 330 or 90 seconds to dry the third-to-last dish (three times), and so on. This computation could be expressed as follows:

 

 

                        Time (n dishes) = n  ( 30 seconds wash time) +

                                                  = 30n + 30n

                                                  = 15n2 + 45n seconds

 

If there were 30 dishes to wash, the first approach would take 30 minutes, whereas the second (careless) approach would take 247.5 minutes. The more dishes we wash the worse that discrepancy becomes.

 

One might assume that, with the advances in the speed of processors and availability of large amounts of inexpensive memory, algorithm analysis would no longer be necessary. However, nothing could be farther from the truth. Processor speed and memory cannot make up for the differences in efficiency of algorithms.

 

For every algorithm we want to analyze, we need to define the size of the problem. For our dishwashing example, the size of the problem is the number of dishes to be washed and dried. We also must determine the value that represents efficient use of time or space. For time considerations, we often pick and appropriate processing step that we’d like to minimize, such as our goal to minimize the number of times a dish has to be washed and dried. The overall amount of time spent at the task is directly related to how many times we have to perform that task. The algorithm’s efficiency can be defined in terms of the problem size and the processing step.

 

·        Consider an algorithm that sorts a list of numbers into increasing order. One natural way to express the size f the problem would be the number of values to be sorted.

·        The processing step we are trying to optimize could be expressed as the number of comparisons we have to make for the algorithm to put the values in order.

·        The more comparisons we make, the more CPU time is used.

·        A growth function shows the relationship between the size of the problem (n) and the value we hope to optimize.

·        This function represents the time complexity or space complexity of the algorithm.

 

The growth function for our second dishwashing algorithm is

 

                                    t( n ) = 15n2 + 45n

 

However, is not typically necessary to know the exact growth function for an algorithm. Instead, we are mainly interested in the asymptotic complexity of an algorithm. That is, we want to focus on the general nature of the function as n increases. This characteristic is based on the dominant term of the expression – the term that increases most quickly as n increases. As n gets very large, the value of the dishwashing growth function approaches n because the term grows much faster than the n term. The constants and the secondary term quickly become irrelevant as n increases.

 

The asymptotic complexity is called the order of the algorithm. Thus, our dishwashing algorithm is said to have order n time complexity, written O(n2).          This is referred to as Big O( ) or Bog-Oh notation.

 

 

 

Growth Function

Order

t(n)=17

O(1)

t(n)=20n -5

O(n)

t(n)=12n log n + 100n

O(n log )

t(n)=3n2 + 5n – 2

O(n2)

t(n)=2n + 18n2 + 3n

O(2n)

 

 

 

                             Some growth functions and their asymptotic complexity

 

 

               

 

 

Comparing Growth Functions

Once again, one might assume that, with the advances in the speed of processors and the availability of large amounts of inexpensive memory, algorithm analysis would no longer be necessary. However, nothing could be farther from the truth. Processor speed and memory cannot make up for the differences in efficiency of algorithms.

 

 

Another way of looking at the effect of algorithm complexity was developed by Aha, Hopcroft, and Ullman (1974). The table bellow compares four algorithms with various time complexities and the effects of speeding up the processor by a factor of 10.

 

                     

                        Increase in problem size with a ten-fold increase in processor speed

 

Algorithm A1 with a time complexity of n, is indeed improved by a factor of 10. However, algorithm A2, with a time complexity of n2, is only improved by a factor of 3.16. Similarly, algorithm A3 is only improved by a factor of 2.15. For algorithms with exponential complexity, in which the size variable is in the exponent of the complexity term, the situation is far worse. In the grand scheme of things, if an algorithm is inefficient, speeding up the processor will not help.

 

The figure bellow illustrates various growth functions graphically. Note that when n is small, there is little difference between the algorithms. That is, if you can guarantee a very small problem size (5 or less), it doesn't really matter which algorithm is used. However, as n gets larger the differences between the growth functions become obvious.

 

 

                             

 

 

 

Analyzing Loop Execution

To determine the order of an algorithm, we often have to determine how often a particular statement or set of statements gets executed.

Therefore, we often have to determine how many times the body of a loop is executed. To analyze loop execution, first determine the order of the body of the loop, and then multiply that by the number of times the loop will execute relative to n. Keep in mind that n represents the problem size.

Assuming that the body of a loop is O(1), then a loop such as this:

 

for ( int count = 0; count < n; count++ )

{

/* some sequence of O(1) steps */

}

 

 

would have O(n) time complexity. This is due to the fact that the body of the loop has O(1) complexity but is executed n times by the loop structure. In general, if a loop structure steps through n items in a linear fashion and the body of the loop is O(1), then the loop is O(n). Even in a case where the loop is designed to skip some number of elements, as long as the progression of elements to skip is linear, the loop is still O(n). For example, if the preceding loop skipped every other number, the growth function of the loop would be nl2, but since constants don't affect the asymptotic complexity, the order is still O(n).

 

Let's look at another example. If the progression of the loop is logarithmic such as the following:

 

count = 1

while (count < 0)

{

count *= 2;

/* some sequence of O(1) steps */

}

 

then the loop is said to be O(log n). Note that when we use a logarithm in an algorithm complexity, we almost always mean log base 2. This can be explicitly written as O(log2n). Since each time through the loop the value of count is multiplied by 2, the number of times the loop is executed is log2n.

 

 

 

 

Nested Loops

A slightly more interesting scenario arises when loops are nested. In this case, we must multiply the complexity of the outer loop by the complexity of the inner loop to find the resulting complexity. For example, the following nested loops:

for (int count = 0; count < 0; count++)

{

for (int count2 = 0; count2 < 0; count2++)

{

/* some sequence of O(1) steps */

}

}

 

would have complexity O(n2). Both the inner and outer loops have complexity n), which, when multiplied together, results in O(n2).

 

What is the complexity of the following nested loop?

 

for ( int count = 0; count < n ;  count++ )

{

for ( int count2 = count; count2 < n; count2++ );

{

/* some sequence of O(1) steps */

}

}

 

In this case, the inner loop index is initialized to the current value of the index for the outer loop. The outer loop executes n times. The inner loop executes n times the first time, 0-1 times the second time, etc. However, remember that we are only interested in the dominant term, not in constants or any lesser terms. If the progression is linear, regardless of whether some elements are skipped, the order is still O(n). Thus the resulting complexity for this code is O(n2).

 

 

 

 

Questions

  1. What is the difference between the growth function of an algorithm and the order of that algorithm?
  2. Why does speeding up the CPU not necessarily speed up the process by the same amount?

 

Exercises

  1. What is the order of the following growth functions?
    1. 10n2 + 100n + 1000
    2. 10n3 – 7
    3. 2n + 100n3
    4. n2 log n

 

  1. Arrange the growth functions of the previous exercise in ascending order of efficiency for n=10 and again for n=1,000,000.
  2. Write the code necessary to find the largest element in an unsorted array of integers. What is the time complexity of this algorithm?
  3. Determine the growth function and order of the following code fragment:

 

for (int count=0; count < n; count++)

{

            for (int count2=0; count2 < n; count2=count2  2)

            {

                        /* some sequence of O(1) steps */

            }

}

 

  1. Identify the Big O notation for the following table:

 

n

O(       )

O(       )

O(       )

O(       )

16

4

16

256

216

100

7

100

104

2100

1000

10

1000

106

21000