This is my question and I've managed to bring out an answer for part a, but for part b I'm not really confident about my answer of part b.

In a recent court case, a judge cited a city for contempt and ordered a ﬁne of \$2 for the ﬁrst day. Each subsequent day, until the city followed the judge’s order, the ﬁne was squared (i.e., the ﬁne progressed as follows: \$2, \$4, \$16, \$256, \$65,536,...). a. What would be the ﬁne on day N? b. How many days would it take for the ﬁne to reach D dollars (a Big-Oh answer will do)?

Ans a : 2^(2^n-1)

For answer b, I made the following program to find the big Oh.

``````for (int i=0; i<n-1; i++)
{
result = 2 * result;

}   printf("%d\t", result);
for (int j =0; j <result;j++)
{
res = 2 * res ;

}

printf("%d\n", res);
``````

I have calculated the big Oh of the first loop to be Sumation of n And since the second loop runs 2^n-1 times the first loop, its big Oh is 2^n and adding them both they become (2^n) + n

Personally I would ignore "(a Big-Oh answer will do)" and give an exact answer. You have the formula for fine after n days

fine = 2^(2^(n-1))

The second question is how many days will it take to for the fine to reach D (i.e. when fine = D) all you …

## All 3 Replies

Personally I would ignore "(a Big-Oh answer will do)" and give an exact answer. You have the formula for fine after n days

fine = 2^(2^(n-1))

The second question is how many days will it take to for the fine to reach D (i.e. when fine = D) all you have to do is re-arrange your equation to find n in terms of fine (logarithms will help here)

ln(fine) = (2^n-1)ln(2)
ln(fine) / ln(2) = 2^(n-1)
ln(ln(fine) / ln(2)) = (n-1)ln(2)

Giving

n = (ln(ln(fine) / ln(2)) / ln(2)) + 1

This is simpler to read if written in terms of log to base 2

n = log2(log2(fine)) + 1

If you really want your big O notation look at your original formula and notice you are using an exponential of an exponential of days so O(e ^ e ^ x), remembering that Big O notation is an indication of how quickly something gets big.

I haven't analyzed Banfa's answer for correctness, but it looks good! IE, in n days, 2^(n-1) == really big number for medium sizes of n. Example, 2^(16-1) == 32768, 2^(32-1) == 2147483648. So, in 31 days (about a month) they'd owe about a billion \$. :-) Of course, in a 30 day month, it would be 1/2 that, and in a leap-year February (29 days) "only" \$250M, and \$125M in a normal February... :-)

Thank you guys

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.