Given the following algorithm, matching each statement to the correct sequence for complexity analysis.

procedure Alg3(A): A is a list of n integers

1    for i = 1 to n-1 do

2        x=aix=aix = a_i

3        j = i − 1

4        while (j ≥≥\geq 0) do

5            if x≥ajx≥ajx \geq a_j then

6                break

7            end if

8            aj+1=ajaj+1=aja_{j+1} = a_j

9            j = j − 1

a        end while

b        aj+1=xa_{j+1} = x

c    end for

d    return A

What is the Big-O notation that can best describe the following algorithm?

procedure Alg2(x, A): A is a list of n integers

1    i = 0

2    while (i < n)

3        if (x == A[i])

4            break

5        end of if

6        i = i + 1

7    end of while

8    if (i < n)

9        location = i

a    else

b        location = -1

c    end of if

d    return location

What is the Big-O notation that can best describe the following algorithm?

procedure bubble_sort(A)

1    for i = 0 to n-2 do

2        for j = 0 to n-i-2 do

3            if aj>aj+1a_j > a_{j+1} then

4                swap aja_j and aj+1a_{j+1}

5        end of for j

6    end of for i

7    return A

What is the Big-O notation that can best describe the following algorithm?

procedure Alg1(A): A is a list of n integers

1    m = A[0]

2    for i = 1 to n-1

3        if m < A[i] then 

4            m = A[i]

5        end of if

6    end of for

7    return m

Prove that f(n)=3n2+6n+9f(n)=3n2+6n+9f( n ) = 3n^2+6n+9 is not O(n)O(n)O( n )

Matching each statement with the correct sequence in a formal proof.

Prove that f(n)=5n2+6n+7f(n)=5n2+6n+7f( n ) = 5n^2+6n+7 is O(n2)O(n2)O( n^2 )

Matching each statement with the correct sequence in a formal proof.

If an algorithm with input integer nn can return the result in f(n)=3.3×10−8×nf( n ) = 3.3 \times 10^{-8} \times n seconds.

How long can this algorithm finish when n=230n=2^{30}?

If an algorithm with input integer nn can return the result in f(n)=3.3×10−10×2nf( n ) = 3.3 \times 10^{-10} \times 2^n seconds.

How long can this algorithm finish when n=63n=63?

If an algorithm with input integer nn can return the result in f(n)=3.3×10−10×n2f( n ) = 3.3 \times 10^{-10} \times n^2 seconds.

How long can this algorithm finish when n=230n=2^{30}?

Suppose a sequence is defined as:

a0a0a_0 = 9

ai=2×ai−1+5a_i = 2 \times a_{i-1} + 5 for all i≥1i \geq 1

Determine aia_i when ii is 3.