Stack Expansion

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\alpha , 3\alpha , 4\alpha ... \] for some positive constant \(\alpha\).

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

×

Problem Loading...

Note Loading...

Set Loading...