MATH 140 Analysis of Algorithms

Estimate the order of growth for the following method as a function of n. 

Do not multiply your answer by a coefficient not equal to 1.   Example:  If the number of operations equals n/2 your answer should be the order of growth = n.

public static int getSum(int[] arr) 
{

        int sum = 0;

        int n = arr.length;

        for (int i = 0;  i < Math.sqrt(n); i++) {

            sum += arr[i];

        }

        return sum;

    }

n

n²

lg(n)

sqrt(n)sqrt(n)sqrt(n)

sqrt(n)sqrt(n)sqrt(n)

Estimate the order of  growth for the following method as a function of n.

Do not multiply your answer by a coefficient not equal to 1. Example: If the number of the operations equals n/2 your answer should be the order of growth n.

public static int getSum2(int[] arr) {     

 int sum = 0;

        int n = arr.length;

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

            for (int j = n ; j  > 0; j = j - 2)

                sum += arr[j];

        return sum;

    }

n²

lg(n)

sqrt(n)sqrt(n)

n

n²

What is the order of growth for the following function of input size: 2N²+1

2N²+1

2N²

N²

1

N²

What is the order of growth for the following function of the input of size N.

3N^4/5 + 2N³ + N

1

N

N^4 + N³

N^4

N^4

What is the order of growth for the following function of the input size of N.

(1+1/N)(1+2/N)

1

1/N

1/N²

N

1

Find the order of growth for finding the largest value in an array with n elements. Assume n is a positive integer.

n

N²

1

sqrt(n)

1

Find the order of growth for pushing a value onto a Stack.

n

N²

1

sqrt(n)

1

Tilde approximate is the same as Big Oh notation
True or False

False

Find the Tilde approximation and the order of growth for the following functions:
N³/6 - N²/2 + N/3

Tilde approximation: ~N³/6

Order of growth: N³/6

Tilde approximation: ~N/3

Order of growth: N³/6

Tilde approximation: ~N³

Order of growth: N³

Tilde approximation: ~N³/6 

Order of growth: N³

Tilde approximation: ~N³/6 

Order of growth: N³

Big oh notation delve lopes the --------  of an algorithm.

The upper bound

The lower bound

The average

The optimal

The upper bound

How many instructions as a function of N do we have in the following nested loop:

for(row=0;row<N;row++)
{
   for (col=o;col<N;com++)
   {
      p=a[row][col]
   }
}

3N² + 4N + 2

3N + 4

N²

3N³ + 4N² + 2N

3N² + 4N + 2

The purpose of analyzing algorithms is to avoid algorithms with _____.

low memory usage and high runtime

high memory usage and low runtime

high memory usage and high runtime

high computational efficiency

high memory usage and high runtime

------ scenario of an algorithm happens when the algorithm is working on the easiest input or the minimum number of operations.

best case

best time

average case

worst case

best case

An algorithm is developed to find a name starting with a given letter in a list.

What is the worst case scenario to find a name starting with letter 'X' in a list of student names.

The first name in the list begins with “X.”

No names in the list begin with “X”

The last name in the list begins with “X.”

No answer text provided.

The first name in the list begins with “X.”

Consider the following list. Using linear search, how many characters needs to be checked to locate the letter 'M'?

'A', 'C', 'E', 'G', 'I', 'K', 'M', 'O', 'Q', 'S', 'U', 'W', 'Y'

1

3

5

7

7

Which of the following statements is true about the order of growth of linear and binary search algorithms?

Linear search is linear and Binary search is quadratic.

Linear search is linear and Binary search is logarithmic.

Linear search and Binary search are both logarithmic.

Linear search and Binary search are both linear.

Linear search is linear and Binary search is logarithmic.

In the worst case, how many letters do you need to check to find a specific letter in an ordered list of English letters.

11

26

9

4

4

Which statement describes the steps in a Binary Search algorithm?

1. BS checks the first element in the list, if the key is equal to the first element then the search stops.

2. Else BS check the last element. If the last element is equal to the key then the search stops. 

3. BS repeats step 1 and 2 till the key is found.

1. BS algorithm finds the middle element in the list.

2. If the key is less than the middle element, BS continues on the right sublist.

3. Else if the key is greater than the middle element, BS continues on the left sublist.

4. Else the key is equal to the middle element of the list.

1. BS algorithm finds the middle element in the list.

2. If the key is less than the middle element, BS continues on the left sublist.

3. Else if the key is greater than the middle element, BS continues on the right sublist.

4. Else the key is equal to the middle element of the list.

1. BS starts from the first element in the list,

2. If the first element is equal to the key, the search stops.

3. Else BS checks  the rest of the list till finds the key or the list is over.

1. BS algorithm finds the middle element in the list.

2. If the key is less than the middle element, BS continues on the left sublist.

3. Else if the key is greater than the middle element, BS continues on the right sublist.

4. Else the key is equal to the middle element of the list.

Which of the following statements is true with reference to an algorithm’s runtime?

The runtime of an algorithm is independent of the speed of the processor.

The runtime of an algorithm is analyzed in terms of nanoseconds.

A single algorithm can execute more quickly on a faster processor.

The runtime of an algorithm is independent of the input values.

A single algorithm can execute more quickly on a faster processor.

An algorithm finds the minimum number in a 2-D array. This is a time constant algorithm.

True or False

False

The order of growth of which code is constant?

N is input size.

int COUNT = N;
int y = 0;
for(int i = 0; i < COUNT; i++)
    y += i;

int[] arr = new int[30];
for(int i = 0; i < arr.length; i++)
      arr[i] = 0;

int sum = 0;
for (int i = 0; i < N/2; i+=2)
    sum += i

Scanner sc = new Scanner(System.in);
string str1 = sc.nextLine();
string str2 = sc.nextLine();
string str3 = concat(str1, str2)

int[] arr = new int[30];
for(int i = 0; i < arr.length; i++)
      arr[i] = 0;

The number of instructions in the most time consuming part of a code as a function of input size N is:

2N³ - 6N² + N

What is the order of growth of the code

2N³

2N³ - 6N²

N³

N²

N³

The order of growth of which code is not constant?

Accessing an element of an array

Push operation on a stack

Inserting a new Node to a Linked List

Finding the total of all elements in an array.

Finding the total of all elements in an array.

Which option is not correct about worst case of an algorithm.

Provides a guarantee for all inputs.

Determined by “most difficult” input.

Upper bound on cost

Lower bound on cost

Lower bound on cost

We consider the CPU type when we analyze an algorithm,

True or False

False

Give the order of growth (as a function of N) of the running times of the following code fragment.

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for (int j = 0; j < N; j++)
      sum++;

linearO(N)

logarithmic or O(log^n)

linearithmic or O (N log^n)

O(N²) quadratic or

linearithmic or O (N log^n)