What is the time complexity of the better method

Assignment Help Basic Computer Science

Reference no: EM13698828

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?

Reference no: EM13698828

Questions Cloud

Enter the decimal value of the binary number : computer generates a random sequence of 0s and 1s creating a binary number. In each round, the computer adds one more bit to the previous sequence, only displaying the added bit.

Data streams and how are they used to facilitate storage : What are Java data streams and how are they used to facilitate storage and retrieval of persistent objects?

Which of insertion sort-mergesort and quicksort are stable : A sorting algorithm is described as stable if equal elements are in the same relative order in the sorted sequence as in the original sequence.

Prepare a binary to decimal memory game : The computer generates a random sequence of 0s and 1s creating a binary number - prepare a binary to decimal memory game.

What is the time complexity of the better method : 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.

Find the smallest positive integer : Find the smallest positive integer whose digits add up to 23. The second smallest positive integer whose digits add up to 23 is 689.

Determines the largest value : Write a program Largest that reads three integers from the user and determines the largest value - Write a program InOrder that reads three integers from the user and prints the three integers in sorted order.

Write a program to play a game of craps : Write a program to play a game of "craps," a dice game popular in casinos. Here are the rules - Use functions appropriately. The program should allow the user to play another round.

Find the initial concentration of the weak acid or base : Question- Find the initial concentration of the weak acid or base in an aqueous solution of pyridine (C5H5N) with a pH of 8.81. Kb=1.80x10^-9. Answer in units of mol/L.

User Account

All Pages