2

I have a sorted array of length n and I am using linear search to compare my value to every element in the array, then i perform a linear search on the array of size n/2 and then on a size of n/4, n/8 etc until i do a linear search on an array of length 1. In this case n is a power of 2, what are the number of comparisons performed?

Not sure exactly if this response is correct but I thought that the number of comparisons would be

T(2n) = (n/2) +(n/4) + ... + 1.

My reasoning for this was because you have to go through every element and then you just keep adding it, but I am still not sure. If someone could walk me through this I would appreciate it

Improve this question
1
  • You use "lineary search" or "binary search"? Commented Feb 3, 2013 at 21:51

1 Answer 1

Reset to default
4

The recurrence you have set up in your question is a bit off, since if n is the length of your input, then you wouldn't denote the length of the input by 2n. Instead, you'd write it as n = 2k for some choice of k. Once you have this, then you can do the math like this:

  • The size of half the array is 2k / 2 = 2k-1
  • The size of one quarter of the array is 2k / 4 = 2k-2
  • ...

If you sum up all of these values, you get the following:

2k + 2k-1 + 2k-2 + ... + 2 + 1 = 2k+1 - 1

You can prove this in several ways: you can use induction, or use the formula for the sum of a geometric series, etc. This arises frequently in computer science, so it's worth committing to memory.

This means that if n = 2k, your algorithm runs in time

2k+1 - 1 = 2(2k) - 1 = 2n - 1

So the runtime is 2n - 1, which is Θ(n).

Hope this helps!

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you for the response, do you mind explaining a bit how you got 2^(k+1 )- 1 and that it runs in time 2n-1?
@Masterminder- I've just updated my answer to explain this. Hope this helps!
Yes Thank you that helps a lot. So if I were to use like another type of searching like binary search to compare every element then how would that look like? I would still be performing it on a sorted array of length n and then an array of size n/2, etc. I know it runs in log(n) so would it look like something log(2^k) + log(2^(k-1))+... ?
@Masterminder- Exactly right. And that simplifies down to k + (k - 1) + (k - 2) + ... + 2 + 1 = k(k + 1) / 2. Since 2^k = n, this means that k = Theta(log n), so the overall runtime is Theta((log n)^2).
Just want to clarify to prove that result through geometric series :) (so i can see for myself). number of elements = n, a=2^k, r= 1/2?? Can you correct me if I am wrong. The formula to use would be a(1-r^n)/(1-r) since r is 0<r<1. I want to figure out how you go this 2^(k+1) -1
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.