试图找到递归的渐近运行时遇到麻烦

我正在尝试找出算法的运行时间.它是通过将问题分成2/3个集合(这是CLR排序)而起作用的.我在解决它时遇到了一些麻烦，这就是我遇到的问题:

I'm trying to figure out the runtime of an algorithm. It is a sort which works by dividing the problem up into sets of 2/3's (it's the CLR sort). I'm having some trouble coming up with it, this is what I have:

T(n)= 3T([2n]/3)+1(1是因为除了递归调用外，可能进行或可能不进行一次交换.假设已完成，则仍然是不变的费用.)

T(n)=3T([2n]/3)+1 (the 1 is because aside from the recursive calls, there is one exchange which may or may not be made. Assuming it is done, it is still only a constant cost.)

T(n)=3T([2([2n]/3+1)]/3+1)+1
T(n)=3T([2([2([2n]/3+1)]/3+1)]/3+1)+1
T(n)=3T([2([2([2([2n]/3+1)]/3+1)]/3+1)]/3+1)+1

等...直到我们可以假设，在某个时候我们终于达到了T(n)的基本情况，并为该运行时获得了恒定值1.这给了我们:

etc......until we can assume that at some point we finally hit the base case for T(n) and get a constant value of 1 for that runtime. This gives us:

3([2([2([2([2(...........)]/3+1)]/3+1)]/3+1)]/3+1)+1 with logn terms (that's the "......." in the middle). This gives:

3*(2n/3+1)^(logn)+1*logn

3*(2n/3+1)^(logn)+logn           

然后我认为，既然日志的基数为2n/3 + 1，我们可以将其简化为3 * logn + logn，那么我们可以这样做. (我一直听到，在进行渐进表示法时，我们选择的日志的基础无关紧要....)

Then I think that since, if the base of the log were 2n/3+1, we could simplify it to simply be 3*logn+logn, we can do so. (I keep hearing that when doing asymptotic notation, the bases of the logs which we chose don't matter....)

这将变为4logn.系数下降，变成简单的logn.

This becomes 4logn. The coefficient drops away to become simply logn.

这是正确的吗?我不确定我是否正确扩展了它，或者我的日志操作是否合法...此外，最终结果是什么-big-O，theta等.我不确定我在看什么. ..

Is this correct? I'm not sure if I expanded this properly, or if my log manipulations were legal...Also, what is this final result--big-O, theta, etc. I'm not sure what I'm looking at...

谢谢.