CODEWITHSUNDEEP
algorithmbig-oanalysis
Masterminder
Masterminder

Reputation: 1135

Examining an algorithm on a sorted array

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

Upvotes: 2

Views: 66

Answers (1)

templatetypedef
templatetypedef

Reputation: 372852

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!

Upvotes: 4

Related Questions