Big-o complexity problem - Linear cumulative power

user_756908 0
Viewed 121

Background

I am trying to work through some problems I found from Stanfords "Design & Analysis of Algorithms" course from 2013. In particular, problem 3 from problem set 1 here.

In summary it states:

  • You are stuck on a desert island with a radio that can transmit a distress signal at integer power levels (i.e. 1W, 2W, 3W, etc.).
  • If you transmit a signal with high enough power, you will receive a response and be rescued.
  • Unfortunately you do not know how much power, n, is needed.

The problem requests you design an algorithm that uses Θ(n)W total power.

Being a 5pt question from problem set 1, I presume this is easier than I am finding it.

My question is

...what is this algorithm?....or how can I change my thinking to find one?

Where I'm stuck

The question states that the strategy "just increase power by 1 watt each time" will result in an Θ(n^2)W total power. Indeed, this is true, as the total power used by any n is n * (n+1) / 2.

However, I can't think of any strategy that isn't:

  • greater than linear; or
  • a strategy where I cheat by "not doing anything for a few consecutive n's".

Also, if I ignore the discreteness of the radio for a minute and analyse the problem as a continuous linear function, the total power should be generalisable to a function g(n) of the form g(n) = Kn + B (where K and B are constants). This linear function would represent the integral of the function we need to use for controlling the radio.

Then, if I take the derivative of this function, dg(n)/dn, I'm left with K. I.e. If I want to have linear total power, I should just drive the radio at a constant power for n times...but this would only result in a rescue if I happened to guess K correctly the first time.

EDIT

Yes, I had already thought of doubling etc....but the answers here pointed out the error in my thinking. I had been trying to solve the question "design an algorithm that has linear cumulative power consumption"...which I think is impossible. As pointed out by the answers, I should have thought about it as "for a given n, design an algorithm that will consume Kn"...i.e. what the question posed.

big-o complexity-theory algorithm
2 Answers

Well here is a simple algorithm and complexity analysis:

  • Initialy try with power=1W
  • If it wasn't received try with power=2*previous_power until it is received

Complexity:

So basically we stop when power p>= n, where n is the desired threshold. We know that:

p>=n and p/2<n => n<=p<2n

In order to reach the pW (i.e the desired level in order to be received) this means you tried previously with p/2, prior to that p/4... and initially with 1, so let's sum up all the steps:

1+2+4+...+p/2+p -> 2*p ~ Θ(p) = Θ(n)
user_66713420

I've read the assignment... It states that the radio is capable of transmitting in integers, but it doesn't mean you should try it one by one and go over all the integers until n.

Well, I could give you the answer but I'll try just to lead you to think about it on your own:

Please notice that you need to transmit a signal equal or greater than n, so there is no way you are "going to far". Now, with the concepts of complexity, if you go over all the signals you'll get a series of (1+2+3+...+n) which equals to Θ(n^2), try to think of a pattern which you can skip some of those and getting a series that results a sum of Θ(n).

This task is similar to searching algorithms which naively goes for Θ(n^2), but there are algorithms reduced to less than that - you should go and explore how they work :)

If you want an approach for an answer:

You can start with 1W and each step double it for the next transmit. That way you will do log(n) attempts, and each attempt costs i which i is the power of that attempt. So the cumulative power will be something like that: (1+2+4+8+16+...+n) which equals to 2n-1 and fits the requirement of Θ(n)

user_57500160
Related