Dynamic Memory Allocation
Question: 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 organize the free lists and give the time complexities for
Part 1: Free to add a block to the free lists
Part 2: malloc to find a "best-fit" block from these lists.
Show any drawbacks that any method might have.
A Numerical Puzzle
Question: You are given an array containing n integers. You are asked to find 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.
Part 1: Find a way to solve this problem that is O(n2).
Part 2: Can you do better? What is the time complexity of the better method?
I cannot seem to get this to work for some reason could somebody provide me a code to compare and test?