Allocation Procedure: Analyzing Time Complexity

[evinda]

Hello! (Wave)

I am looking at the following exercise.
Use a [m]Divide-and-Conquer[/m] procedure for the computation of the [m] i [/m] greatest element at a row of integers.
Analyze the asymptotic time complexity of your algorithm.

Hint : Use the allocation procedure.I thought to sort the integers using the algorithm [m]Merge sort[/m].
But how could we use the hint? What is the [m] allocation procedure [/m] about?

 

[I like Serena]

Hello! (Wave)

I am looking at the following exercise.
Use a [m]Divide-and-Conquer[/m] procedure for the computation of the [m] i [/m] greatest element at a row of integers.
Analyze the asymptotic time complexity of your algorithm.

Hint : Use the allocation procedure.I thought to sort the integers using the algorithm [m]Merge sort[/m].
But how could we use the hint? What is the [m] allocation procedure [/m] about?

Hey evinda! (Smile)

Merge sort has complexity O(n log n). The exercise is to do it more efficiently.
I believe you're supposed to create a binary tree.
The hint probably means you're to use [m]malloc()[/m] to construct the tree. (Wasntme)

 

[evinda]

Hey evinda! (Smile)

Merge sort has complexity O(n log n). The exercise is to do it more efficiently.
I believe you're supposed to create a binary tree.
The hint probably means you're to use [m]malloc()[/m] to construct the tree. (Wasntme)

So could we create a binary tree as follows?

struct node{
   int data;
   struct node *left;
   struct node *right;
}tree;tree *insert(tree *root, tree *element) {
  if (root == NULL)
     return element;
  else {
     if (element->data > root->data) {
        if (root->right != NULL) root->right = insert(root->right, element);
        else root->right = element;
     }
     else {
        if (root->left != NULL) root->left = insert(root->left, element);
       else root->left = element;
   }
   return root;
 }
}

struct node *create(int v) {
   struct node *tmp;
   tmp = (struct node*)malloc(sizeof(struct node));
   tmp->data = v;
   tmp->left = NULL;
   tmp->right = NULL;
   return tmp;
}Node;

int Algorithm(int array[0...n-1]){
    int i;
    tree T;
    Node temp_node;
    for (i=0; i<n; i++){
          temp_node = create(array[i]);
            T = insert(T, temp_node);
        }
}

How could we use a Divide-and-Conquer procedure for the computation of the [m]i[/m] greatest element, taking into consideration the binary tree? (Thinking)

 

[evinda]

Is the following algorithm right?

Algorithm ith(A,low,high){
   q=partition(A,low,high);
   if (high-i+1==q) return A[q];
   else if (high-i+1<q) ith(A,low,q-1);
   else ith(A,q+1,high);
}

Or don't we consider that [m] partition [/m] is a Divide and Conquer procedure? (Thinking)