CODEWITHSUNDEEP
javasorting
Popokoko
Popokoko

Reputation: 6543

General: Search time in algorithm

i have a general question (taken from some computer science test) i'd like to get an explanation for, the question was:

Sorted array given a particular size, and suppose we use the fastest method in computer science to find values ​​in the array. In this method, the search time of any element is no more than N seconds. Now we multiply the size of the array. The search time of any element in the array will be at most:

Answer: N+1.

Can anyone please give me a full explanation why this is the answer? and why isn't it 2*N ?

Thanks.

Upvotes: 0

Views: 86

Answers (2)

František Hartman
František Hartman

Reputation: 15086

I think that the sentence "In this method, the search time of any element is no more than N seconds" is there just to confuse you.

I will ignore the seconds and consider it as O(N) steps.

There is an algorithm to find the element in log(x) steps (binary search - see the other answe). So

log2(x) = N

log2(2*x) = N+1

(I know this is not very precise and formal, but I hope you get the idea).

Upvotes: 3

mishadoff
mishadoff

Reputation: 10789

I suppose they mean binary search algorithm as fastest method for searching in sorted array. It is algorithm of type "divide and conquer", so for one step of such algorithm we reduce searching area by half.

Example: Let's define one step in our algorithm take 1 unit of time

array = [1 2 3 4 5 6 7 8], to find = 7
We test our value as the last element in first array.
1 step: divide into [1 2 3 4] and [5 6 7 8], 4 < 7, our value in second array
2 step: divide into [5 6] and [7 8], 6 < 7, our value in second array
3 step: divide into [7] and [8], 7 = 7, we found it.

It is how binary search works and consumes 3 units of time. Now imagine we doubled array to [1..16], we need 1 more step to reduce array to previous one, so we need 4 units of time.

Upvotes: 1

Related Questions