Question

Consider the following description of an algorithm: first, sort the data. Then, search for the target data element using binary search. If we assume that the sorting algorithm will take O(n2) time, what is the best big O estimate of the total algorithm time?

O(log n)

O(n^2 log n)

O(n)

O(n^2)

Answer 1

A program with sorting searching algorithm which uses an algorithm of O(n^2) and binary search to search for an algorithm will have a time complexity of O(n^2).

Explanation:

Suppose the following algorithm:

for i <- 1 to n do

            for j <-1 to n do

                        //some O(1) expressions

            end for

end for

for i <- 1 to n

            //some O(1) expression

end for

This algorithm has two 2 parts, 1st part contains a nested loop and other a single loop. 1st part will have a time complexity of O(n^2). Second part will have a time complexity of O(n)

So the total time complexity will be O(n^2 + n) which is ultimately O(n^2).

Similarly, The total time complexity of your algorithm will be O(n^2 + logn) (binary search time complexity is O(logn)) which is ultimately O(n^2)