Allocation Procedure: Analyzing Time Complexity

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Procedure
In summary, the algorithm ith() is a Divide-and-Conquer procedure that works by finding the ith greatest element in a sorted array.
  • #1
evinda
Gold Member
MHB
3,836
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
  • #2
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)
 
  • #3
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)
 
  • #4
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)
 

FAQ: Allocation Procedure: Analyzing Time Complexity

What is time complexity in relation to allocation procedures?

Time complexity refers to the measure of how much time an algorithm takes to run as the input size increases. In the context of allocation procedures, it is used to analyze how long it takes for the procedure to allocate resources based on the input size.

How is time complexity determined for allocation procedures?

Time complexity is determined by analyzing the algorithm and its steps to determine the number of operations it performs based on the input size. This is usually represented using Big O notation, which gives an upper bound on the number of operations as the input size approaches infinity.

What is the significance of analyzing time complexity for allocation procedures?

Analyzing time complexity allows us to understand the efficiency of an allocation procedure and how it will perform as the input size increases. This information is crucial for choosing the most efficient algorithm for a specific use case and optimizing the allocation process.

What are some factors that can affect the time complexity of allocation procedures?

The time complexity of an allocation procedure can be affected by the type of algorithm used, the data structure of the input, and the implementation of the algorithm. Other factors such as the hardware and software environment can also impact the time complexity.

Can the time complexity of an allocation procedure be improved?

Yes, the time complexity of an allocation procedure can be improved by using more efficient algorithms, optimizing the implementation, and choosing appropriate data structures for the input. However, it is important to note that there is no one-size-fits-all solution and the best approach will depend on the specific use case and constraints.

Similar threads

Back
Top