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

  Find the probability that all the bulbs selected are good

A bin contains 62 light bulbs of which 7 are defective. If 4 light bulbs are randomly selected from the bin with replacement, find the probability that all the bulbs selected are good ones. Round to the nearest thousandth if necessary.

  Find the largest possible volume of the box

If 2000 square centimeters of material is available to make a box with a square base and an open top, find the largest possible volume of the box.

  Systems of linear equations with infinite solution

In Algebra, when using the addition method, how can you tell if a system of linear equations has infinitely many solutions?

  How should this be done

A piece of wire is 20 cm long. It is to be cut into two pieces (not necessarily of the same length). One piece is ti be bent into a square and the other into a circle. How should this be done so that the resulting sum of the areas of the two objec..

  Find the direction the plane is actually headed

A plane is heading due south with an airspeed of 264 mph. A wind from a direction of 59 degrees is blowing at 13 mph. Find the direction the plane is actually headed. (Note that bearings are measured from north, clockwise.

  Determining mathematics-calculus in commerce

If the current levels of input are x = 10 and y = 20, use calculus to estimate the change in input y that should be made to offset an increase of 0.5 in input x so that output will be maintained at its current level.

  What dimensions will minimize farmer johns costs

What dimensions will minimize Farmer Johns costs? What are Farmer John's minimum possible costs? Verify that you have found an absolute minimum(be complete)

  What is the largest rectangle that can be inscribed

What is the largest rectangle that can be inscribed in the first quadrant of the ellipse 9x^2+16y^2=144?

  Find probability of passing reading

Mary is taking courses in both Reading and English. She estimates her probability of passing Reading of 0.4 and English at 0.6 and she estimates her probability of passing at least one of them at 0.8.

  Find the eqation ofa parabola

find the eqation ofa parabola whose foci are (5,2)and whose equation of diectrix is 2x+3y=0

  A population is normally distributed a random sample of

a population is normally distributed. a random sample of size 15 is taken. the sample mean is 75 and the sample

  Interval of convergence and partial fractions

Find the first five terms in the Taylor series about x = 0 for f(x). Find the interval of convergence for the series in part (a).

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