Big Oh notation of two non nested loops

[momal]

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 fine of $2 for the first day. Each subsequent day, until the city followed the judge’s order, the fine was squared (i.e., the fine progressed as follows: $2, $4, $16, $256, $65,536,...). a. What would be the fine on day N? b. How many days would it take for the fine 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

[Banfa]

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.

[rubberman]

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... :-)

[momal]

Thank you guys