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

  Questions on ferris wheel

Prepare a Flexible Budget Gator Divers is a company that provides diving services such as underwater ship repairs to clients in the Tampa Bay area.

  Logistic map

This assignment has two question related to maths. Questions are related to bifurcation cascade and logistic map.

  Finding the probability of cards

This assignment has questions related to probabiltiy.

  Systems of ode

Find all the xed points, and study their stability and Draw the phase portrait of the system, as well as the graphs of the solutions in all relevant cases.

  Derive the boolean expression

Derive the Boolean Expression and construct the switching circuit for the truth table stated

  System of equations

Evaluate which equations are under-identified, just-identified, and over-identified.

  Linear programming problem

Linear programming problem consisting of only two constraints with one objective function.

  Find the natural domain

Find the natural domain of the given functions.

  Introduction to numerical methods

Compute the coecients of the polynomials using the term recurrence relation.

  Chart of the topological manifold

De?nition of smoothness of functions on a smooth manifold is chart independent and hence geometric.

  Mathematics in computing

Questions related on mathematics in computing.

  Complex problems

Complex problems

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