Web.njit.edu



Lab 5

When discussing the efficiency of an algorithm, there are three cases that need to be considered:

• the best case,

• the worst case,

• and the average case.

The best case is how the algorithm will work on the best possible input. The worst case is how the algorithm runs on the worst possible input. And the average case is how it runs on most inputs. When comparing algorithms we very rarely use the best case, often use the average case and sometimes use the worst case.

How efficient is sorting?

Well if we use linear sorting on a list with N elements, we have to do N comparisons followed by N -1 comparisons, followed by N -2 comparisons, followed by . . . all the way down to N –N comparisons.

In total, that is:

N(N + 1)/2 comparisons.

The most significant part of this number is the N2, and we write the number of comparisons as O(N2).

This is known as “Big O” notation.

Linear searching is O(N), and so will be more efficient than linear sorting since N is always smaller than N2.

Binary searching is O(log N), and so is more efficient than either linear searching or linear sorting since log N is smaller than N and N2. However, if we sort with linear sort and then search using binary search, overall that will be less efficient than using linear search.

• 1. O(1) - constant time

• 2. O(logn) - logarithmic time

• 3. O(n) - linear time

• 4. O(nlogn)

• 5. O(nc) - polynomial

• 6. O(cn) - exponential

• 7. O(n!) - factorial

Constant Time  -  In terms of abstract time, constant times means a constant number of operations.

Lab 5

Problem 1: Recursive Linear Search

File IntegerListS.java contains a class IntegerListS that represents a list of integers (you may have used a version of this in an earlier lab); IntegerListSTest.java contains a simple menu-driven test program that lets the user create, sort, and print a list and search for an element using a linear search.

Many list processing tasks, including searching, can be done recursively. The base case typically involves doing something with a limited number of elements in the list (say the first element), then the recursive step involves doing the task on the rest of the list. Think about how linear search can be viewed recursively; if you are looking for an item in a list starting at index i:

_ If i exceeds the last index in the list, the item is not found (return -1).

_ If the item is at list[i], return i.

_ If the is not at list[i], do a linear search starting at index i+1.

Fill in the body of the method linearSearchR in the IntegerList class. The method should do a recursive linear search of a list starting with a given index (parameter lo). Note that the IntegerList class contains another method linearSearchRec that does nothing but call your method (linearSearchR). This is done because the recursive method (linearSearchR) needs more information (the index to start at) than you want to pass to the top-level search routine (linearSearchRec), which just needs the thing to look for.

Now change IntegerListTest.java so that it calls linearSearchRec instead of linearSearch when the user asks for a linear search. Thoroughly test the program.

private int linearSearchR (int target, int lo)

{

if (lo >= list.length)

return -1;

else if (list[lo] == target)

return lo;

else

return linearSearchR(target, lo+1);

}

// ****************************************************************

// IntegerListS.java

//

// Defines an IntegerListS class with methods to create, fill,

// sort, and search in a list of integers. (Version S -

// for use in the linear search exercise.)

//

// ****************************************************************

public class IntegerListS

{

int[] list; //values in the list

// ------------------------------------

// Creates a list of the given size

// ------------------------------------

public IntegerListS (int size)

{

list = new int[size];

}

// --------------------------------------------------------------

// Fills the array with integers between 1 and 100, inclusive

// --------------------------------------------------------------

public void randomize()

{

for (int i=0; i< list.length; i++)

list[i] = (int)(Math.random() * 100) + 1;

}

// ----------------------------------------

// Prints array elements with indices

// ----------------------------------------

public void print()

{

for (int i=0; i 0 and n0 _ 1

such that f(n) + d(n) _ c(g(n) + h(n)) for every integer n _ n0.

f(n) is O(g(n)) means that there exists cf > 0 and an integer n0f _ 1 such that

f(n) _ cf g(n) for every n _ n0f . Similarly, d(n) is O(h(n)) means that there exists cd > 0

and an integer n0d _ 1 such that d(n) _ cdh(n) for every n _ n0d.

Let n0 = max(n0f; n0d), and c = max(cf ; cd). So f(n) + d(n) _ cf g(n) + cdh(n) _

c(g(n) + h(n)) for n _ n0. Therefore f(n) + d(n) is O(g(n) + h(n)).

(b) Show that 3(n + 1)7 + 2n log n is O(n7). Hint: Try applying the rules of proposition.

Solution Let us apply rules of Proposition:

_ log n is O(n) (Rule 10)

_ 2n log n is O(2n2) (Rule 6)

_ 3(n + 1)7 is a polynomial of degree 7, therefore it is O(n7) (Rule 7)

_ 3(n + 1)7 + 2n log n is O(n7 +2n2) (Problem 1.a of this homework)

_ 3(n + 1)7 + 2n log n is O(n7) (Rule 7)

(c) Algorithm A executes 10n log n operations, while algorithm B executes n2

operations. Determine the minimum integer value n0 such that A executes fewer operations than B for n >= n0.

Solution We must _nd the minimum integer n0 such that 10n logn < n2. Since n

describes the size of the input data set that the algorithms operate upon, it will always

be positive. Since n is positive, we may factor an n out of both sides of the inequality,

giving us 10logn < n.Let us consider the left and right hand side of this inequality. These

two functions have one intersection point for n > 1, and it is located between n = 58

and n = 59. Indeed, 10 log 58 _ 58:57981 > 58 and 10 log 59 = 58:82643 < 59. So for

1 _ n _ 58, 10n log n _ n2, and for n _ 59, 10n logn < n2. So n0 we are looking for is

59.

Problem 4:

(a) What does the following algorithm do? Analyze its worst-case running time,

and express it using “Big-Oh" notation.

Algorithm Foo (a, n):

Input: two integers, a and n

Output: ?

k ←0

b ← 1

while k < n do

k ← k + 1

b ← b * a

return b

Solution This algorithm computes an. The running time of this algorithm is O(n)

because

_ the initial assignments take constant time

_ each iteration of the while loop takes constant time

_ there are exactly n iterations

(b) What does the following algorithm do? Analyze its worst-case running time,

and express it using “Big-Oh" notation.

Algorithm Bar (a, n):

Input: two integers, a and n

Output: ?

k ←n

b ← 1

c ← a

while k > 0 do

if k mod 2 = 0 then

k ←k=2

c ← c *c

else

k ← k − 1

b ← b* c

return b

Solution This algorithm does the same thing as the one in 1.a: it computes an. Its

running time is O(log n) for the following reasons:

The initialization and the if statement and its contents take constant time, so we need

to _gure out how many times the while loop gets called. Since k goes down (either gets

halved or decremented by one) at each step, and it is equal to n initially, at worst the loop

gets executed n times. But we can (and should) do better in our analysis.

Note that if k is even, it gets halved, and if it is odd, it gets decremented, and halved

in the next iteration. So at least every second iteration of the while loop halves k. One

can halve a number n at most dlog ne times before it becomes _ 1 (each time we halve a

number we shift it right by one bit, and a number has dlog ne bits). If we decrement the

number in between halving it, we still get to halve no more then dlog ne times. Since we

can only decrement k in between two halving iterations (unless n is odd or it is the last

iteration), we get to do a decrementing iteration at most dlog ne +2 times. So we can have

at most 2dlog ne + 2 iterations. This is obviously O(log n).

[pic][pic][pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download