Examining an algorithm on a sorted array

Question

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(2ⁿ) = (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

• Анатолий: You use "lineary search" or "binary search"?

Answer 1

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 2ⁿ. Instead, you'd write it as n = 2^k for some choice of k. Once you have this, then you can do the math like this:

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

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

2^k + 2^k-1 + 2^k-2 + ... + 2 + 1 = 2^k+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 = 2^k, your algorithm runs in time

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

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

Hope this helps!

• Masterminder: 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?
• templatetypedef: @Masterminder- I've just updated my answer to explain this. Hope this helps!
• Masterminder: 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))+... ?
• templatetypedef: @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).
• Masterminder: 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