1. How many steps are taken in the execution of this loop? Answer...

for (i = 0; i < 10; i++)
{
	ar[i] = i;
}

2. How many steps are taken in the execution of this loop? Precondition: n>0. Answer...

for (i = 0; i < n; i++)
{
	ar[i] = i;
}

3. How many steps are taken in the execution of this loop? Precondition: n>0. Answer...

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

4. How many steps are taken in the execution of this loop? Precondition: n>0. Answer...

for (i = 0; i < n; i++)
{
	ar[i] = i;
	sum += i;
	sum2 += i*2;
	sum3 += i*3;
	sumsq += i*i;
}

5. How many steps are taken in the execution of this code? Precondition: n>0. Answer...

for (i = 0; i < n; i++)
{
	ar[i] = i;
}
for (i = 0; i < n; i++)
{
	br[i][4] = i;
}

6. Which is the loop run time most dependent on?
(a) number of statements in the loop
(b) number of initialization statements in for statement
(c) value of n
 Answer...

We say that the above algorithms require "on the order of n steps", which is expressed using Big-O (pronounced "big-Oh") function. For purposes of this introduction, a polynomial expression for number of steps can be reduced by eliminating coefficients and eliminating all terms except the one with highest power of n. Under Big-O, all the above algorithms are O(n). a.k.a. linear.

 7. How many steps are taken in the execution of this loop? Precondition: n>0. Answer...

for (i = 0; i < n; i++)
{
	for (j = 0; j < n; j++)
	{
		br[i][j] = i+j;
	}
} 

for (i = 0; i < n; i++)
{
	for (j = 0; j < i; j++)
	{
		br[i][j] = i+j;
	}
}

8. For a given n, will this loop run faster than the previous one? Answer...

9. Does this change affect the Big-O running time? Answer...

10. What is the Big-O running time of this method? Precondition: n>0. Answer...

/* a is array of ints, n is number of values stored in array, val is search value. */
boolean find (int a[], int n, int val)
{	
	int i=0;
	boolean found = false;
	while (i < n && found==false)
	{
		if (a[i] == val)
		{
			found = true;
		}
		i++;
	}
	return found;
}

11. Here is pseudo-code (in italics) for a faster version of find. Preconditions: n>0, array is sorted in ascending order. What is its running time? (preview of chapter 11). Answer...

boolean find (int a[], int n, int val)
{	
	Interval = ENTIRE ARRAY;
	boolean found = false;
	while (Interval not empty && found==false)
	{
		if (Interval midpoint value == val)
			found = true;
		else
			if (Interval midpoint value < val)
				Interval = upper half of Interval;
			else 
				Interval = lower half of Interval;
	}
	return found;
}

The running time of some algorithms is not a function of input size, for example an algorithm which does not use iteration (either through loops or recursion). Such algorithms have running time O(1).

Algorithms with running time O(1) are sometimes called constant.
Algorithms with running time O(log n) are sometimes called logarithmic.
Algorithms with running time O(n) are sometimes called linear.
Algorithms with running time O(n²) are sometimes called quadratic.
Algorithms with running time O(2ⁿ) are sometimes called exponential. You will study these in CSC 325.

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )