Consider the algorithm
procedure BS(a[1, ..., n] : array of n numbers) if(n = 1) return; if(n = 2 and a[1] > a[2]) swap(a[1],a[2]); return; s := floor(n/3) BS(a[1, ..., n − s]); BS(a[1 + s, ..., n]); BS(a[1, ..., n − s]); return;
I'm trying to write a recurrence for a function $R(n)$ such that BS runs in $O(R(n))$ time on a size $n$ array. I'm not really sure how I can do that, as I don't entirely understand how the algorithm is working to compute the answer. Can someone perhaps outline what's necessary in order to come up with an accurate solution? In general, what steps should one take to ensure that the running type of some algorithm is captured?