2

Considering a fairly common problem - I am thinking of an integer, can you guess it in O(log n) time given that I will answer to your guesses in "high", "low" or "that's the one!" - I have come across a problem that is a slight variation that has me stumped:

I am thinking of a positive real number between 1 and N. Guess my number to within one decimal place in O(log log log N) time.

I tried solving this by trying to guess 10N instead of N but that would still not give me an O(log log log N) runtime. Any and all views on this are welcome.

Thank you

Rishi
  • 321
  • 2
  • 6
  • 17
  • 1
    hint: X=10+Log(x) ... – Mitch Wheat Jan 02 '14 at 01:10
  • "to within one decimal place" --- I guess this means the right first digit and the right power of ten? And I assume we're given `N`? – Teepeemm Jan 02 '14 at 02:09
  • What's "within one decimal place"? One sig fig? – user2357112 Jan 02 '14 at 04:40
  • 1
    Are you sure about that constraint? O(log log N) seems possible but not O(log log log N). – Mark Ransom Jan 02 '14 at 05:31
  • To my understanding, 'within one decimal place' means the integer part of the number and the value at the 1/10th place. So for number 466.1220, 'within one decimal place' would mean 466.1. Unfortunately, this is a random problem I came across while preparing my algorithms and I have no way of verifying what the line was intended to mean. This is just my understanding. @MarkRansom I came to a similar conclusion too - O(log N) for the integer part and another O(log N) for the decimal part, correct? Like I said though, I have nothing other than the question to go by :) – Rishi Jan 02 '14 at 14:43

2 Answers2

1

Assuming "within one decimal place" means one significant figure, there are O(log(n)) possible guesses between 1 and n. 1, 2, 3, ..., 10, 20, 30, ..., 100, 200, 300, ... A binary search through these possibilities will produce the correct answer in O(log(log(n)) time. For ease of coding, this can be instead done as a binary search for the order of magnitude, followed by a binary search for the first digit. However, it is information-theoretically impossible to use O(log(log(log(n))) guesses to determine one of O(log(n)) possibilities.

Example: I'm thinking of a number between 1 and 10000.

Is it 100? Higher. Is it 1000? Lower. Now we know the order of magnitude.

Is it 500? Higher. Is it 700? Higher. Is it 800? Higher. It's 900.

user2357112
  • 260,549
  • 28
  • 431
  • 505
0

A nominal scale variable (also referred to as a categorical variable) is one in which there is no particular relationship between the different possibilities: for these kinds of variables it doesn’t make any sense to say that one of them is “bigger’ or “better” than any other one, and it absolutely doesn’t make any sense to average them. The classic example for this is “eye colour”. Eyes can be blue, green and brown, among other possibilities, but none of them is any “better” than any other one. As a result, it would feel really weird to talk about an “average eye colour”. Similarly, gender is nominal too: male isn’t better or worse than female, neither does it make sense to try to talk about an “average gender”. In short, nominal scale variables are those for which the only thing you can say about the different possibilities is that they are different. That’s it.

rezaa
  • 1