Asymptomatically tight solution

[torpid notch]

Is this well-defined? What's the domain?

[coarse stratus]

can you expand what u mean by domain and well defined?

[torpid notch]

The domain is what values of n you're allowed to plug in. Can you ever find T(5)?

[coarse stratus]

T(5) would just be T(sqrt(5)) + log_2 5 which would continually drop to sqrt(n) until n is between 1 and 4 which would then give a result of 1

i think

thats what im interpreting the question as

and i am asked to Give asymptotically tight solutions to the following recurrences.

I thought about maybe trying to draw a recursion tree to solve it, but tbh im pretty fuzzy on them so idrk how I would go abt that if thats the way to solve something like this

[torpid notch]

Is n a natural number or a real number?

I suppose it shouldn't really matter, but you probably have different tools to work with in different classes

[coarse stratus]

pretty sure n is just any number between 1-4 so it can be like 1.2, 3, 2.7, etc

[torpid notch]

I would just look at the sequence 2,4,16,256,256^2,...

Does it say somewhere that log is supposed to be log base 2?

[coarse stratus]

we automatically assume log base 2 in my class

[torpid notch]

What class is this?

[coarse stratus]

analysis of algorithms

[dense quartz]

here's what I found

by iterating the process of plugging sqrt(n) in the definition, you can essentially end up with T(n) = T(sqrt(n))+lg(n) = T(n^(1/4)) + 3/2lg(n) = T(n^(1/8)) + 7/8lg(n) etc...

so you see we're descending towards 1 inside T (which I assume to represent a complexity), and approaching 2lg(n) on the other term

so that motivates proving the following statement : for all integers n, T(n) <= 1+2lg(n)

and you can prove that by induction very easily

but what this gives you for this algorithm is that the complexity is O(log(n)) which is pretty good!

though I'd be pretty curious as to what this algorithm does with such a strange recursion expression (if it even exists outside of this exercise lmao)

@coarse stratus ^

[coarse stratus]

yep it gives Theta(log n), not sure what it does , prolly just meant for the exercise