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 'Star maps using Blender'
Blender just recently dropped a new version, 4.5(with 5.0 on the horizon), and within it was a new feature for which I immediately thought of a use for. The new feature was a .csv importer for Geometry nodes. Geometry nodes are a method of modelling that uses a node tree to create 3D models which offers more flexibility than straight modeling does. The .csv importer node allows you to bring in a .csv file and use the data in it to control aspects of your model. So for example, if you...
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
Back
Top