MHB Answer the Ultimate Question: What is the Age of the Oldest Genus?

[evinda]

Hi! (Wave)

We have a machine, that knows the answer to the question: "Which is the age of the oldest genus, that ever existed?". The machine can only give the answers "YES/NO". I want to write an algorithm with time complexity $O(\log n)$, that implements that. So, we don't have a bound for the age, but can only ask $\log n$ questions. How could we do this? (Thinking)

 

[Ackbach]

Hi! (Wave)

We have a machine, that knows the answer to the question: "Which is the age of the oldest genus, that ever existed?". The machine can only give the answers "YES/NO". I want to write an algorithm with time complexity $O(\log n)$, that implements that. So, we don't have a bound for the age, but can only ask $\log n$ questions. How could we do this? (Thinking)

This looks tailor-made for a binary search/bisection method (which is $O(\log(n))$). Your questions will be of the form "Is the age less than x?" You will have to have some a priori bound on the age of the oldest genus in order for it to be truly $O(\log(n))$, otherwise, you'd have to have a linear element in there, which grows faster than the logarithm.

 

[evinda]

This looks tailor-made for a binary search/bisection method (which is $O(\log(n))$). Your questions will be of the form "Is the age less than x?" You will have to have some a priori bound on the age of the oldest genus in order for it to be truly $O(\log(n))$, otherwise, you'd have to have a linear element in there, which grows faster than the logarithm.

So, if the answer will be YES, we will have to call the function for the interval $[0,x-1]$, right? But, what if the answer will be NO?
For which interval would we call the function? (Thinking)

 

[Ackbach]

So, if the answer will be YES, we will have to call the function for the interval $[0,x-1]$, right? But, what if the answer will be NO?
For which interval would we call the function? (Thinking)

I would think of it in terms of lower and upper ends of the current interval of interest. You can see the bisection method here.

 

[evinda]

I would think of it in terms of lower and upper ends of the current interval of interest. You can see the bisection method here.

But, we don't have an upper bound for the age.. How can we find the interval? I haven't understood it... (Thinking)

 

[Ackbach]

But, we don't have an upper bound for the age.. How can we find the interval? I haven't understood it... (Thinking)

Ha. If you believe in an old universe, then pick 100 billion years. If you don't, pick 10,000 years.

 

[evinda]

Ha. If you believe in an old universe, then pick 100 billion years. If you don't, pick 10,000 years.

So, do I have to suppose an upper bound and ask the machine if it is right?

 

[Ackbach]

So, do I have to suppose an upper bound and ask the machine if it is right?

You could try this algorithm:

Let n=0.
Let answer=NO.
while(answer=NO)
   If genus < 10^n years old
     execute bisection algorithm with upper bound 10^n 
        \\ and lower bound 10^(n-1), actually, assuming
        \\ the age is actually older than 1/10 year. 
     set answer=YES.
   else n++
end while

Since you're going up by an order of magnitude each time, it should be an $O(\log(n))$ matter to find an upper bound, so that shouldn't add to your complexity.

 

[I like Serena]

Suppose we start by asking the questions if the age is less than 1, 2, 4, 8, ...
This will take about $\log_2 n$ questions before we get yes.
Now we have an upper bound! (Sun)

We'll need another $\log_2 n$ questions to zoom in, for a total of max $2 \log_2 n$. (Sweating)

 

[evinda]

Suppose we start by asking the questions if the age is less than 1, 2, 4, 8, ...
This will take about $\log_2 n$ questions before we get yes.
Now we have an upper bound! (Sun)

We'll need another $\log_2 n$ questions to zoom in, for a total of max $2 \log_2 n$. (Sweating)

And do we have to suppose an upper bound or don't we have to? (Thinking)

 

[I like Serena]

And do we have to suppose an upper bound or don't we have to? (Thinking)

We don't have to suppose an upper bound. (Mmm)

 

[evinda]

We don't have to suppose an upper bound. (Mmm)

How can we do it otherwise? (Thinking)

 

[I like Serena]

How can we do it otherwise? (Thinking)

By first going up, and doubling the age in every iteration.
That way we'll find an upper bound within $O(\log n)$. (Mmm)

 

[evinda]

By first going up, and doubling the age in every iteration.
That way we'll find an upper bound within $O(\log n)$. (Mmm)

How do we know that we will find an upper bound within $O(\log n)$ ? (Worried)

 

[I like Serena]

How do we know that we will find an upper bound within $O(\log n)$ ? (Worried)

Suppose the age of the oldest genus, that ever existed, is $n=969$.
How many questions would it take to found an upper bound? (Wondering)

 

[evinda]

Suppose the age of the oldest genus, that ever existed, is $n=969$.
How many questions would it take to found an upper bound? (Wondering)

So, you mean that we start asking if the age is $i=1$ and then with the command [m] i=2*i[/m], we double the age in every iteration? (Thinking)

 

[I like Serena]

So, you mean that we start asking if the age is $i=1$ and then with the command [m] i=2*i[/m], we double the age in every iteration? (Thinking)

Well, I would ask the question: "Is the age less than $i$?", as Ackbach suggested.
But yes, that is the way to go. (Mmm)

 

[evinda]

Well, I would ask the question: "Is the age less than $i$?", as Ackbach suggested.
But yes, that is the way to go. (Mmm)

So, would it be like that? (Thinking)

int i=1;
if (age==1) then answer='yes';
else answer='no';
while (answer=='no'){
    i=2*i;
   if (age==i) then answer='yes';
   else answer='no';
   i=i+1
}

If so, how can we find the complexity?

 

[Ackbach]

So, would it be like that? (Thinking)

int i=1;
if (age==1) then answer='yes';
else answer='no';
while (answer=='no'){
    i=2*i;
   if (age==i) then answer='yes';

I wouldn't compare the age to i exactly, the way you're doing here: you're banking on the age being precisely a power of 2. Instead, use the test

if (age <= i) then answer = 'yes';

In general, you should avoid using the == test, particularly for numerical tests. If you can use an inequality, it'll be much better for most cases. The == test is too precise, and may give you negatives inadvertently when you really wanted a positive!

 

[evinda]

I wouldn't compare the age to i exactly, the way you're doing here: you're banking on the age being precisely a power of 2. Instead, use the test

if (age <= i) then answer = 'yes';

In general, you should avoid using the == test, particularly for numerical tests. If you can use an inequality, it'll be much better for most cases. The == test is too precise, and may give you negatives inadvertently when you really wanted a positive!

A ok... (Smile) But, how can find the complexity of this algorithm? (Thinking)

 

[evinda]

You could try this algorithm:

Let n=0.
Let answer=NO.
while(answer=NO)
   If genus < 10^n years old
     execute bisection algorithm with upper bound 10^n 
        \\ and lower bound 10^(n-1), actually, assuming
        \\ the age is actually older than 1/10 year. 
     set answer=YES.
   else n++
end while

Since you're going up by an order of magnitude each time, it should be an $O(\log(n))$ matter to find an upper bound, so that shouldn't add to your complexity.

And if genus $> 10^n$, do we have to assume an other upper boud, for examle $10^{2n}$ ? (Thinking)

 

[Ackbach]

And if genus $> 10^n$, do we have to assume an other upper boud, for examle $10^{2n}$ ? (Thinking)

I'm not sure you've understood the algorithm. Incidentally, my algorithm is essentially the same as I like Serena's; I'm going up by a factor of 10 each time, and he by a factor of 2.

Let us suppose the actual age is 930,000 years. This algorithm would execute the following steps:

n=0
answer = NO
answer == NO (TRUE, so enter while loop)
   age < 1 (FALSE, so enter else part)
   n++ (n is now 1)
   age < 10 (FALSE, so enter else part)
   n++ (n is now 2)
   age < 100 (FALSE, so enter else part)
   n++ (n is now 3)
   age < 1,000 (FALSE, so enter else part)
   n++ (n is now 4)
   age < 10,000 (FALSE, so enter else part)
   n++ (n is now 5)
   age < 100,000 (FALSE, so enter else part)
   n++ (n is now 6)
   age < 1,000,000 (TRUE)
      execute bisection algorithm with upper bound 1,000,000
      and lower bound 100,000
   answer = YES
answer == NO (FALSE, so exit while loop)

So this algorithm won't quit until it finds an upper bound. Because its candidate for the upper bound is increasing by an order of magnitude for each loop iteration, this algorithm (and ILS's) will find an upper bound in $O(\log(n))$ time, where $n$ is the age of the genus.

Incidentally, ILS's algorithm for finding the upper bound might be better overall than mine; his algorithm leaves less for the bisection portion to do; whereas my algorithm is more likely to give a rougher upper bound, leaving more for the bisection part to do. I should think the bisection portion would take more time to execute than the finding of an upper bound, so on balance, it's probably wiser to let the upper bound locating take a tad more time in order to restrict your search better.

 

[evinda]

Algorithm{
  int i=1;
  char answer;
  if (age<=1) then answer='yes';
  else answer='no';
  while (answer=='no'){
          i=2*i;
         if (age<=i) then answer='yes';
        else answer='no';
        i=i+1
  }
}

I haven't still understood why applying the above algorithm we can find in $O(\log n)$ time the answer to our question... (Worried)

 

[I like Serena]

Algorithm{
  int i=1;
  char answer;
  if (age<=1) then answer='yes';
  else answer='no';
  while (answer=='no'){
          i=2*i;
         if (age<=i) then answer='yes';
        else answer='no';
        i=i+1
  }
}

I haven't still understood why applying the above algorithm we can find in $O(\log n)$ time the answer to our question... (Worried)

I'm afraid this algorithm isn't sufficient.
It only finds something like the lowest power of 2 that is an upper bound of the age. (Wasntme)

The number of steps to find it is $\log_2 age$ plus some constant. (Nerd)

 

[evinda]

I'm afraid this algorithm isn't sufficient.
It only finds something like the lowest power of 2 that is an upper bound of the age. (Wasntme)

The number of steps to find it is $\log_2 age$ plus some constant. (Nerd)

Should the algorithm look like that? If so, how could we justify that it has the desired time complexity? (Thinking)

Algorithm{
  int i=1,low=1,high,k;
  char answer;
  printf("Is the age <= 1? \n");
  scanf("%c",&answer);
  if (answer=='yes') {
     printf("The age of the oldest genus, that ever existed is equal 1. \n");
     return;
  }
  else answer='no';
  while (answer=='no'){
          i=2*i;
          printf("Is the age <= %d? \n",i);
          scanf("%c",&answer);
  }
  high=i;
  k=BinarySearch(low,high);
  printf("The age of the oldest genus, that ever existed is equal %d. \n",k);
}

BinarySearch(low,high){
  if (high<low) return 0;
  int mid=low+floor((high-low)/2);
  char answer;
  printf("Is the age equal to %d \n", mid);
  scanf("%c",&answer);
  if (anwer=='yes') return mid;
  else {
         printf("Is the age <= %d \n", mid);
         scanf("%c",&answer);
         if (answer=='yes') BinarySearch(low,mid-1);
         else BinarySearch(mid+1,high);
  }
}

 

[I like Serena]

Should the algorithm look like that?

That looks about right. (Smile)

... although it won't compile and run as C code. Did you try? (Worried)

If so, how could we justify that it has the desired time complexity? (Thinking)

I see you're using a binary search algorithm now.
What is its time complexity? (Wondering)

And how is that justified? (Wondering)