What is the big-oh complexity for a push

Assignment Help Mathematics
Reference no: EM13924349

1. How many cost units are spent in the entire process of performing 32 consecutive push operations on an empty array which starts

out at capacity 8, assuming that the array will double in capacity each time a new item is added to an already full dynamic array?

As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for a push?

2. How many cost units are spent in the entire process of performing 32 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array?

As N (ie. the number of pushes) grows large, under this strategy for resizing,

what is the big-oh complexity for a push?

3. Suppose that a dynamic array stack doubles its capacity when it is full, and shrinks (on Pop only) its capacity by half when the array is half full or less.

Can you devise a sequence of N push() and pop() operations which will result in poor performance (O(N^2) total cost)?

How might you adjust the array's shrinking policy to avoid this? (Hint: You may assume that the initial capacity of the array is N/2.)

 

 

Reference no: EM13924349

Questions Cloud

What two components are involved in valuation procedure : What two components are involved in the two-part valuation procedure? Given the two components in the valuation procedure, which is more volatile?
How normal distribution can be used in operations enviroment : The normal distribution is a family of distributions that is often used to model operational processes. Based on your readings for this module, give one example, different from those supplied in the overview, of how the normal distribution can be ..
What variables affect the aggregate operating profit margin : What variables affect the aggregate operating profit margin, and how do they affect it? What variables determine the level and changes in the market earnings multiplier?
Problem releated to relationship-inheritance : Grading: For each programming assignment, you are graded by explaining and demoing your code to a TA. You must demo your program BEFORE the next assignment is due, and if you fail to do so, you will automatically lose 50 points! Your job is to con..
What is the big-oh complexity for a push : Suppose that a dynamic array stack doubles its capacity when it is full, and shrinks (on Pop only) its capacity by half when the array is half full or less.
Perpetual inventory method : what are the steps to recording and adjusting the lifo Fifo and weighted average. Also what do we record and what don't we record on the perpetual inventory method.
Solve the problem in matlab to find the slowness map : Calculate the maximum and minimum oil in place (STOOIP) for this field -  Use the generalized linear least square formulation to solve the problem in MATLAB to find the slowness map. Can you identify the location and extend of oil spill?
Defined pension plan : Data are available for Joey CO's defined pension plan
What would you expect to happen to unit labor cost : It is estimated that next year hourly wage rates will increase by 7 percent and productiv- ity will increase by 5 percent. What would you expect to happen to unit labor cost?

Reviews

Write a Review

Mathematics Questions & Answers

  Fundamental set of solution

Verify that y1(t) =(1/(t^3)) and y2(t) = (ln(t))/(t^3) are solutions to (t^2)y''+7ty'+9y = 0, t>0. Do y1, y2 for a fundamental set of solutions? Give a reason for your answer and show all steps.

  Find the lengths of both circular arcs of the unit circle

find the lengths of both circular arcs of the unit circle connecting the point 10 and the endpoint of the radius that

  Round to the nearest whole number

Colombia has a population density of about 43 people/km2 and a population of about 48,929,706. What is the approximate area of Colombia? Round to the nearest whole number

  What is the shortest distance to shore

if a ship is off shore a length of 18 miles to observe, bearings are 35E & 37 E. what is the shortest distance to shore.

  How should the string be cut so the sum of the areas

A 42 inch piece of string is cut into two pieces. One piece is used to form a circle and the other to form a square. The two peices of string are not equal in length. How should the string be cut so the sum of the areas is a minimum?

  Contingency was conducted to see whether their opinions on

the contingency table below shows the results of a random sample 200 state representatives that was conducted to see

  Determining inverse hyperbolic function

Solve the equations i. 6sinh theta - 4cosh theta-3=0 correct to 3 decimal places

  For what value of x is the perimeter largest

For what value of X is the perimeter largest?

  The manufacturer would like to set inventory levels such

the monthly sales of mufflers in the richmond va area follow the normal distribution with a mean of 1200 and a standard

  What is the area between a raw score

What is the area between a raw score of 113 and 126 in a normal distribution with a mean of 100 and a standard deviation of 10 ?

  What was the principal amount of the loan

The total accrued interest owed as of August 31 on a loan advanced the preceding June 3 was $169.66. If the variable interest rate started at 8 3/4% interest, rose to 9% effective July 1, and increased another ½% effective July 31, what was the pr..

  Specify the sequence of transformations

specify the sequence of transformations that will yield the graph of the given function from the graph of f(x) =x^3

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd