Stack Expansion

Computer Science Level 4

In an array-based implementation, whenever a stacks become full, it is common to just double its size. Suppose that instead of doubling every-time, we start with an array of size α \alpha and increase the array size by the sequence 2 α , 3 α , 4 α . . . 2\alpha , 3\alpha , 4\alpha ... for some positive constant α \alpha .

In such a stack, suppose we execute n n push operations. The total cost complexity g ( n , α ) g(n,\alpha) of this operation can be asymptotically expressed as a function g g in terms of n n and α \alpha . If g ( n , α ) = O ( n x α y ) g(n,\alpha) = O( \large{ n^x \alpha^{y} )} for some exponents x x and y y . What is the value of 10 x 2 y 2 10x^2 y^2 ?


The answer is 40.

View wiki
Thaddeus Abiy by Thaddeus Abiy , 25, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Brock Brown
Oct 2, 2015

Python 3.4: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
def g(n, a):
    operations = 0
    stack_size = a
    times_increased = 1
    for push in range(n):
        if stack_size == 0:
            times_increased += 1
            stack_size = a * times_increased
            operations += stack_size
        operations += 1
        stack_size -= 1
    return operations
print ("Answer:", g(20, 10))

0 Helpful 0 Interesting 0 Brilliant 0 Confused

I changed the wording of the question a little bit because I wasn't sure what size the stack was supposed to start out as. Let me know if my rewording is wrong.

Brock Brown - 5 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...