1.

What is the worst-case order of complexity for an algorithm that does the following: Finding the first occurrence of a given target in an integer array.

Select one:

a. O(n)

b. O(log n)

c. O(n log n)

d. O(n²)

2.

What is the running time of the following algorithm (in the worst case) expressed in terms of n?

for i 1 to n do if A[i] = x then return i elseif A[i] < x then i i + 1 else return x not found return x not found

Select one:

a. T(n) = n

b. T(n) = n log n

c. T(n) = 2n

d. T(n) = n²

^3.

Big Oh defines an Upper Bound for performance, which means that it provides a worse case analysis for ANY input value of n.

Select one:

True

False

4.

The upper bound always specifies the worse case performance of an algorithm within the constraints of the constants, which are usually represented by c and n0.

Select one:

True

False

5.

Counting only assignment statements as operations, what is the order of complexity of the following code fragment as a function of n? x = 1; while (x < n) x = x + x;

Select one:

a. O(1)

b. O(n)

c. O(log n)

d. O(n²)

6.

Counting only assignment statements as operations, what is the exact number of operations executed by the following code fragment in terms of n?

x = n; while (x > 0) { z = 0; while (z <= 6) z = z + 2; x = x - 1; }

Select one:

a. 6n+1

b. n²

c. 2(6n)

d. 6n

7.

What is the order of complexity of the following code fragment as a function of n? x = n; while (x > 0) { z = 0; while (z <= 6) z = z + 2; x = x - 1; }

Select one:

a. O(n)

b. O(log n)

c. O(n log n)

d. O(n²)