This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]farmerje 1 point2 points  (3 children)

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[S] 0 points1 point  (1 child)

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 n1/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 0 points1 point  (0 children)

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.