MHB Allocation Procedure: Analyzing Time Complexity

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Procedure
AI Thread Summary
The discussion focuses on using a Divide-and-Conquer approach to find the i-th greatest element in an array of integers, with a hint to utilize an allocation procedure. Participants suggest that instead of using Merge sort, which has a time complexity of O(n log n), a more efficient method involving a binary tree should be employed. The allocation procedure likely refers to using dynamic memory allocation (malloc) to construct the binary tree. A proposed algorithm for finding the i-th greatest element involves a partitioning method, raising questions about whether partitioning qualifies as a Divide-and-Conquer technique. The conversation emphasizes the need for a more efficient solution than sorting the entire array.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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? :confused:
 
Technology news on Phys.org
evinda said:
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? :confused:

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)
 
I like Serena said:
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?
Code:
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;
 }
}
Code:
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;

Code:
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)
 
Is the following algorithm right?

Code:
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)
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
Back
Top