1. Modern object-oriented software makes extensive use of the malloc and free op
ID: 3550275 • Letter: 1
Question
1.
Modern object-oriented software makes extensive use of the malloc and free operations. Unfortunately, they are generally quite expensive (in time) and thus efficient routines are important.
free places freed blocks into free lists. In order to re-use memory as much as possible, malloc will generally search the free lists for a block before requesting another one from the operating system (a very expensive exercise!). A best-fit algorithm searches for the smallest free block into which the requested block will fit.
Suggest a number of ways in which free could organise the free lists and give the time complexities for
Describe any drawbacks that any method might have.
2.
Explanation / Answer
Modern object-oriented software makes extensive use of the malloc and free operations. Unfortunately, they are generally quite expensive (in time) and thus efficient routines are important.
free places freed blocks into free lists. In order to re-use memory as much as possible, malloc will generally search the free lists for a block before requesting another one from the operating system (a very expensive exercise!). A best-fit algorithm searches for the smallest free block into which the requested block will fit.
Suggest a number of ways in which free could organise the free lists and give the time complexities for
Answer:-
1. free to add a block to the free lists :-
Time Complexity :- O(1) constant time
reason : because in main memory , OS don't add free block to free list . OS just need to reset its tag. so that same block will availabel for memory allocation.
2. malloc to find a "best-fit" block from these lists. :-
Time Complexity: O(n) linear time
reason : because in main memory allocated data in block randomly . so it take linear time .
Drawback : if we take first fit at the place of best fit then it will take less time compair to best fit. and usualy now days memory are cheap. so we need to focus in time factor and first fit is good choice.if you want longterm profit then choose worst fit algorithm because usualy during execution of program it expad . and we donot need to reallocate memory for that program.
2. You are given an array containing n integers. You are asked to determine if the list contains two numbers that sum to some arbitrary integer, k. For example, if the list is 8, 4, 1and 6 and k = 10, the answer is "yes", because 4+6 = 10.
Hint: Consider sorting the array first.
Answer:-
a. for that u have to use array of that number
for(i=0;i<n;i++)
{
for(j=i+1;j<n;ij++)
{
if(arr[i]+arr[j]==k)
print("Yes");
}
}
it take O(n2) time.
b. to make it better
first we have to sort the array which will take O(nlogn) by merge sort. then make new array for storing successive pair which take O(n) time
for(i=0;i<n-1;i++)
new_arr[i] = arr[i]+arr[i+1];
now we have to find the element k in new array new_arr through binary search which take O(logn);
so Total Time Complexity= O(nlogn) + O(n) + O(logn) =O(nlogn)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.