Ansh2rock
BAN USER@Chennavarri: good job. But if i have to merge 2 arrays of size n/2, then there will b totally n-1 comparisons in the worst case making it O(n).
Coming back to ur solution, to begin with we have 2 sorted arrays of k elements...merging them will take O(2k)...to generalize...if we have n/k sorted arrays of size k each...then at each step we will compare ((n/k)*k)=n elements making it of O(n)complexity...and there will b totally log(n/k) such steps...therefore the complexity of this solution should be O(n log n/k)...
in case of merge sort k=1 therefore O(n log n)
Correct me if i m wrong...
@Anonymous: Thanks for explanation. But going with ur explanation itself, it means that totally 8k elements will b compared and there r totally log8 such steps. Therefore the complexity should b O(8k log8). correct me if i m wrong...
now as u said, i will replace 8 with 'n/k'. then the complexity turns out to b: O((n/k)*k log 8)=O(n log 8)
Am I right???
really sorry for putting the code before testing. Have learned my lesson. finally the code after removing all the bugs is as follows:
- Ansh2rock March 20, 2011int search(tree *node, char key)
{
int l=0;
static char ch= 'n';
if(!node)return -1;
else
{
if(node->data == key) ch='y';
else
{
l=search(node->left, key);
if(ch=='y')return l+1;
l=search(node->right, key);
if(ch=='y')return l+1;
}
return l;
}
}