A note on two non-nested loops

Question

This is my question, and I managed to get the answer for part a, but for part b I am not very sure of my answer to part b.

In a recent court case, a judge quoted the city for contempt and ordered a fine of $ 2 on the first day. Each subsequent day, until the city followed the order of the judges, the finish was squared (i.e. the result was as follows: $ 2, $ 4, $ 16, $ 256, $ 65536, ...). a. What will be day N day? b. How many days will it take to get to D dollars (Big-Oh answer)?

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 calculated the big Oh of the first cycle, which will be the sum of n And since the second cycle runs 2 ^ n-1 times the first cycle, its big Oh is 2 ^ n and adding them both they become (2 ^ n) + n

Answer 1

, - O (N)

int days=5;
int fine = 2;
for(int i=0; i<days-1; i++)
   fine =  fine * fine;

cout << fine;

Answer 2

n-1 , - 2^(n-1) . (n-1) + 2^(n-1) = O(2^n + n) = O(2^n).

, , . , D . a): O(log log D) (, $65536 log(log(65536)) + 1 ).

Answer 3

- . Big O - , .

:

2     = 2^1  = 2^(2^0)
4     = 2^2  = 2^(2^1)
16    = 2^4  = 2^(2^2)
256   = 2^8  = 2^(2^3)
65536 = 2^16 = 2^(2^4)

a.

n 2^(2^(n-1)).

:

pow(2, pow(2, n-1));

b.

x = log2 (log2 D) + 1

"+ 1", .
, .

Now in a large O entry, this will be O (log (log)), which describes how the value grows. This means that when the input (D in this case) is multiplied by n, the value of the function will increase no more than log(log n)once.