Question

QUESTION 8

1. What is the worst-case complexity of line 7 of function bar?

1 2 int bar (int* A, int* B, int N) { int count = 0; for (int i = 0; i < N; ++i) O vouw int x = A[i]; int pos = binarySearch (B, N, x); if (pos >= 0 && B[pos] == x) 10 ++count; 12 13 return count; 14 -}

A.

O(1)

B.

O(N)

C.

O(i)

D.

O(log N)

E.

O(sqrt N)

F.

O(A[i])

G.

O(N sqrt N)

H.

O(N log N)

I.

O(N^2)

J.

O(i^2)

K.

None of the above

QUESTION 9

1. What is the worst-case complexity of lines 6-11 of function bar?

	A.	O(1)
	B.	O(N)
	C.	O(i)
	D.	O(log N)
	E.	O(sqrt N)
	F.	O(A[i])
	G.	O(N sqrt N)
	H.	O(N log N)
	I.	O(N^2)
	J.	O(i^2)
	K.	None of the above

QUESTION 10

1. What is the worst-case complexity of lines 4-12 of function bar?

	A.	O(1)
	B.	O(N)
	C.	O(i)
	D.	O(log N)
	E.	O(sqrt N)
	F.	O(A[i])
	G.	O(N sqrt N)
	H.	O(N log N)
	I.	O(N^2)
	J.	O(i^2)
	K.	None of the above

Answer 1

QUESTION 8
Time complexity of binary search is O(logn)
Line 7 runs for n times.
So, total time complexity = O(nlog(n))
Answer:
O(N log N)

QUESTION 9
Time complexity of sequentialOrderSearch is O(n)
Each Line from 6-11 runs for n times.
So, total time complexity = O(n*n) = O(n^2)
Answer:
O(N^2)

QUESTION 10
Time complexity of sequentialOrderSearch is O(n)
Each Line from 4-12 runs for n times.
So, total time complexity = O(n*n) = O(n^2)
worst-case complexity of lines 4-12 of function bar = O(n^2) 
Answer:
O(N^2)