For problems 1, 2 and 3, provide your answers in the file problems123.docx Add your code to the file Lab2.java.

Guidelines:

Do not use static variables in class Lab2 to implement recursive methods.

Problem 1 (20 points)

1. Using Big Oh notation, indicate the time requirement for each of the following tasks in the worst case. Describe which operations are assumed to take constant time to .

a. After arriving at a party, you shake hands with each person there. n is the number of persons in the party.

b. Each person in a room shakes hands with everyone else in the room. n is the number of persons in the room.

c. You climb a flight of stairs. n is the number of stairs

d. After entering an elevator, you press a button to choose a floor. n is the number of floors

e. You ride the elevator from the ground floor up to the nth floor.

f. You read a book twice. n is the number of pages in the book

Using Big Oh notation, indicate the time requirement of each of the following tasks in the worst case.

g. Display all the integers in an array of integers.

h. Display all the integers in a chain of linked nodes.

i. Display the nth integer in an array of integers.

j. Compute the sum of the first n even integers in an array of integers.

Problem 2 (10 points)

Indicate the order of the following growth functions using < (e.g. n < n²)

a. n² log n

b. n

c. n²/ log n

d. n!

e. (1.5)ⁿ

d. 3ⁿ

Problem 3 (5 points)

What is the worst case runtime complexity of the following code in terms of n

for (int pass = 1; pass <= n; pass++) {

for (int index = 0; index < n; index++) {

for (int count = 1; count < 10; count++) {

// constant time operation

} // end for

} // end for

} // end

Problem 4 (20 Points)

Implement a recursive method min that accepts an array and returns the minimum element in the array. The recursive step should divide the array into two halves and find the minimum in each half.

Demonstrate the output of min on the array int [] a = { 2, 3, 5, 7, 11, 13, 17, 19, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 23, 29, 31, 37, 41, 43 }

Problem 5 (20 Points)

You have been offered a job that pays as follows:

On the first day, you are paid 1 cent, on the second day, 2 cents, on the third day, 4 cents and so on. In other words, your pay doubles every day. Write a recursive method computePay that for a given day number computes the pay in cents.

Assume that you accumulate all the money that you are paid. Write a recursive method computeSavings that computes the sum that you have accumulated on a given day. Show the output of computePay and computeSavings for day number 39.

Problem 6 (25 Points)

Write a recursive method countSubstrings that counts the number of non-overlapping occurrences of a string s2 in a string s1. Use the method indexOf() from String class.

As an example, with s1=abab and s2=ab, countSubstrings returns 2. With s1=aaabbaa and s2=aa, countSubstrings returns 2. With s1=aabbaa and s2=AA, countSubStrings returns 0.

Show the output on the following strings:

s1 = Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities. Java applications are typically compiled to bytecode (class file) that can run on any Java Virtual Machine (JVM) regardless of computer architecture. Java is a general-purpose, concurrent, class-based, object-oriented language that is specifically designed to have as few implementation dependencies as possible. Java is currently one of the most popular programming languages in use, particularly for client-server web applications, with a reported 10 million users.

s2= Java.