Boston University / CLA
Computer Science Dept

CLA CS-101: Introduction to Computers


Introduction

A class was given two quizes. Upon surveying the students in the class, most said that the second quiz was "harder" than the first. What makes a test harder than another? Here are some possible answers: Problems to be solved on a computer are not very different when it comes to comparing them. They are either unsolvable or solvable. And if they are solvable, the algorithms nedded to solve them may differ in terms of how much time they need and how much space they need. Thus, the difficulty of a solvable problem could be measured or estimated by figuring out how much time and how much space will be needed to solve them. These attributes are called the space and time complexity of an algorithm. We will talk about these later. But first, we must introduce the notion of problem size.

Problem Size

When one writes a program, it is usually intended to solve a number of similar problems. For example, when one writes a program to compute the average test scores for a particular class, the same program could be used to average out the scores of other tests in the same course, or even in other courses. The only difference between the different uses of that program may be the "size" of the class. Averaging out the test scores for a 200-student class involves more work than a averaging out the test scores for a 100-student class. The number of students in the class (i.e. the number of test scores that must be averaged out) is an example of a problem size.

To evaluate the complexity of a program is to study how the space/time requirements of the program change with the problem size.


Space Complexity

Unlike humans, computers don't use "paper" they use "memory". Thus, the amount of space they need to solve a problem (through the execution of a program) is measured by the least number of bits (or bytes) they have to use.

Let's look at an example. Suppose we want to write a program to compute the sum of a list of numbers. The program goes into a loop (for a predetermined number of iterations equal to the size of the list, for example 100 or 200, ... etc.) asking the user to enter a number and keeps adding these numbers. What is the space complexity of that program?

There are three simple steps that one should follow:

Now, let's apply the above steps to the example at hand.

Time Complexity

Again, let's look at the same example. Suppose we want to write a program to compute the sum of a list of numbers. The program goes into a loop (for a predetermined number of iterations equal to the size of the list, for example 100 or 200, ... etc.) asking the user to enter a number and keeps adding these numbers. What is the time complexity of that program?

There are three simple steps that one should follow:

Now, let's apply the above steps to the example at hand.

Some Common Relationships

In the above analysis we have encountered two types of relationships: constant and linear. What other possibilities exist? Well, there are lots and lots of possibilities. Here we focus on some important/popular ones.

[ ... To be Continued ... ]


(C) Copyright 1995.
This document has been prepared by Professor Azer Bestavros <best@cs.bu.edu>.

Created on: April 13, 1995.
Updated on: April 12, 1995.