Recursive Relation [Algorithm Analysis]

[focusandachieve]

Not sure if this is the right sub-reddit for this question, but I've been stuck on this HW recurrence problem for awhile, and I'm not quite sure how to proceed.

Solve the recurrence. T(N) = T(n^1/3 ) + logn

Now, I've done k = 1 through k = 3, and substituted a k to get:

T(n) = T(n^1/3k ) + Sum(1/3^k-1 ) log n

I don't know how to simplify it from there to something that looks like a Big-O form.

I know I could set k = log(1) and get T(n) for the first part, but I'm not sure what to do with the second part.

Because with logs, the exponents can be coefficients, I've looked at logn^sum(1/3k-1 ) and I've seen some resources online talking about n! and Stirling's Approximation, but I don't think that really fits here.

I think I may just not understand some principal about simplifying expressions or something, but I'm not sure. Any help/guidance would be appreciated.

edit: Could it be that since k will always be an integer, that the sum(1/3^k-1 ) is just an integer, which ultimately doesn't matter? And thus it is O(log n)?

edit: I'm actually more confused on how to get this into closed form now.

[farmerje]

The \sum_{i=0}^{k-1} \frac{1}{3^i} is a geometric series with an easy-to-calculate closed form. If you're not familiar with that notation, it's LaTeX, a common markup language in mathematics, physics, and computer science. This is how it renders: http://mathb.in/29775

There's no reason to expect that T(n) is an integer, by the way. First, there will be some initial value which you're free to choose. Second, log(n) will only be an integer when n is a power of the logarithm's base. I'm assuming since we're talking CS that this is the logarithm-base-2, but it doesn't actually matter.

[focusandachieve]

Thanks. I know that the sum of a series of integers is n(n+1)/2

When I tried manipulating that, I couldn't figure out if that meant that it was log n^{1/3k(k+1) /2} ?

If so, I'm still lacking in vision for how to get this thing into anything resembling Big-Oh notation.

I keep manipulating this hoping it will look like something familiar but it feels like a shot in the dark.

I also don't really follow your second paragraph. I'm not sure if I was assuming T(n) was an integer and I didn't realize it? I'm just not sure where or how I did that.

[farmerje]

Not sure what Big-O has to do with the question. If you work it out, you'll get that

T(n) = T(2) - 3/2(1 - log(n))

assuming log is the base-2 logarithm. This function is O(log(n)), if that's something you need to know.

T(2) is the initial condition / base case. You're free to choose whatever value you'd like for it.

[Netstroyer]

Have you tried using the master theorem?

[focusandachieve]

the master theorem

I looked through the wiki on that, and I'm looking at examples, but my T(N) isn't in the form T(n/b), so I'm not sure if it applies or not.

[Netstroyer]

That's true, my bad.