CODEWITHSUNDEEP
algorithmcode-analysis
Sid Chaudhry
Sid Chaudhry

Reputation: 104

Counting steps to form a recurrence relation of an algorithm

I am new to algorithm analysis stuff. I just wrote a divide and conquer algorithm which should find a max number from an array in O(n) time and i am stuck at forming it's recurrence.

Following is my algorithm. 

int findMax(int *A, int S, int E){

    if(S == E){        //1 unit of time
        return A[S];
    }
    else if(S == (E-1)){  // 1 unit of time
        if(A[S] > A[E]){  // 1 unit of time
           return A[S];
        }
        else{
           return A[E];
        }
    }

    mid = (S+E)/2;            // 1 unit of time     
    L = findMax(A, S, mid);
    R = findMax(A, mid+1, E);   // 1 unit of time 

    if(L > R){          // 1 unit of time
       return L;
    }
    else if(R > L){     // 1 unit of time
       return R;
    }

}

Please make me correct if i am wrong.

Recurrence that i formed is:

T(n) = 2T(n/2)+7

Am i correct adding up all units cost 7?

Please help me out with this. Thanks.

Upvotes: 0

Views: 132

Answers (1)

Selçuk Cihan
Selçuk Cihan

Reputation: 2034

First of all, not all the code paths are returning, let's modify the algorithm's last if/else statement as follows:

if(L > R){          // 1 unit of time
   return L;
}
else {     // 1 unit of time
   return R;
}
  • T(1) = 1 : This just makes the first comparison and succeeds.
  • T(2) = 3 : This will make three comparisons to find the max of two items.
  • T(N) = 2*T(N/2) + 4, for N > 2

The last one is as follows:

+1 for first if comparison, which will fail
+1 for the else if part of the first comparison block, which will also fail
+1 for computing the middle element
+2*T(N/2) for the recursive parts
+1 for the last comparison (single if)

Upvotes: 1

Related Questions