is it legit calculation of time complexity

Question

I have the following function, and I need to find the Theta Notation:

void aux(int n){
    for(int i = n; i>2; i = sqrt(i))
        printf("*");}
void f1(int n){
aux(n);
aux(n*n);
aux(n*n*n);}

I can assume that sqrt(i) has the time complexity of Theta(1).

I watch the series as it goes like that:

i = n^(1/(2^0)), n^(1/(2^1)), n^(1/(2^2)), ... , n^(1/(2^k))

and there for:

2 = n^(1/2^k) -> 1/2^k = log(n) -> 1/log(n) = 2^k

and now:

k = log(1/log(n)) = log((log(n))^(-1)) = -1*log(log(n)) =Theta(log(log(n))

I do know that the final solution IS Theta(log(log(n)) but I want to know that my calculation is correct and it's ok to say that:

-1*log(log(n)) = Theta(log(log(n))

I did look up at: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm?rq=1 but I would like to know about my calculation. — David, Sep 10 '20 at 12:10
You realize this is integer fixed point arithmetic, yeah? `n^(1/2^i)` gives `n^0` gives `1` for the vast majority of your calculations. — Lundin, Sep 10 '20 at 13:07
Yes, I just want to show the series, and how I proceed with my calculation — David, Sep 10 '20 at 14:10
But none of it makes sense in a C programming context, because you aren't using floating point. The compiler may be smart enough to inline the sqrt call and then you can toss all timing calculations out the window, because a loop like `for(int i = n; i>2; i = 1)` will just be removed and the only thing remaining of your program after optimization is some printf call printing a star. — Lundin, Sep 10 '20 at 14:18
I really don't understand how is this relevant to my question. all I asked that if it' ok to assume that `-1*log(log(n)) = Theta(log(log(n))` — David, Sep 10 '20 at 15:56

score 1 · Accepted Answer · answered Sep 10 '20 at 20:45

First of all, there might be a mistake in the calculations. The working in the question shows

2 = n^(1/2^k) -> 1/2^k = log(n) -> 1/log(n) = 2^k

However

2 = n^(1/2^k) -> 1/2^k = log(base n) 2 -> log(n) = 2^k

So you get k=+log(logn) and not -log(logn). Negative time complexity would mean your program takes negative time to run.

So, yeah, the algo is theta(log(logn))

1 Answers1