Calculating runtime in recursive algorithm

Question

Practicing recursion and D&C and a frequent problem seems to be to convert the array:
[a1,a2,a3..an,b1,b2,b3...bn] to [a1,b1,a2,b2,a3,b3...an,bn]
I solved it as follows (startA is the start of as and startB is the start of bs:

private static void shuffle(int[] a, int startA, int startB){  
        if(startA == startB)return;  
        int tmp = a[startB];  
        shift(a, startA + 1, startB);  
        a[startA + 1] = tmp;  
        shuffle(a, startA + 2, startB + 1);  
    }  

    private static void shift(int[] a, int start, int end) {  
        if(start >= end)return;  
        for(int i = end; i > start; i--){  
            a[i] = a[i - 1];   
        }       
    }

But I am not sure what the runtime is. Isn't it linear?

When you say runtime you mean time complexity, right?

keyser
– keyser

2012-12-26 12:55:12 +00:00
Commented Dec 26, 2012 at 12:55 — keyser
– keyser, Commented Dec 26, 2012 at 12:55
@Keyser:Yes the O(f(n))

Cratylus
– Cratylus

2012-12-26 13:34:16 +00:00
Commented Dec 26, 2012 at 13:34 — Cratylus
– Cratylus, Commented Dec 26, 2012 at 13:34

amit · Accepted Answer · 2012-12-26 12:57:44Z

2

Let the time consumed by the algorithm be T(n), and let n=startB-startA.

Each recursive invokation reduces the run time by 1 (startB-startA is reduced by one per invokation), so the run time is T(n) = T(n-1) + f(n), we only need to figure what f(n) is.

The bottle neck in each invokation is the shift() operation, which is iterating from startA+1 to startB, meaning n-1 iterations.

Thus, the complexity of the algorithm is T(n) = T(n-1) + (n-1).

However, this is a known Theta(n^2) function (sum of arithmetic progression) - and the time complexity of the algorithm is Theta(N^2), since the initial startB-startA is linear with N (the size of the input).

answered Dec 26, 2012 at 12:57

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Cratylus Over a year ago

I see.But why is the runtime reduced only by 1?The algorithm move 1 elements at each step (plus the shifting) and does this for half the elements (N/2) in total.Am I wrong on this?

amit Over a year ago

@Cratylus: The algorithm as a function of startB-startA is reduced by 1 every iteration because the difference startB-startA is reduced by one, and the stop clause is when this difference is 0. Note that the T(n) is NOT in the terms of the size of the array, but in terms of startB-startA, now - assume startB-startA == N/2 (Where N is the size of the array), it still gets you Theta((N/2)^2) = Theta(N^2/4) = Theta(N^2) solution.

Cratylus Over a year ago

Ah!My original intention is to do the check: if(startB==a.length)return; that is why I got confused with your point.Now I am not sure if algorithm is correct.I mean It eventually stop when the difference is 0 as you correctly point out, but how do I know that this is the correct thing to do?

amit Over a year ago

@Cratylus: This is a different question, and you might want to post it as such. Though I don't think there will be any difference, as I see it (unless for some off by one error), the two suggested stop clauses should be identical, and the complexity remains the same.

Cratylus Over a year ago

I will post a different question for an alternative.For the runtime, your answer is very clear!Thank you!+1 by me

Collectives™ on Stack Overflow

Calculating runtime in recursive algorithm

1 Answer 1

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Related