# Tag Info

8

If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.

5

That's probably a typo or poor wording -- in the quote, "has" should be "is".

4

$\alpha$ indicates the Inverse Ackermann Function: $\alpha(n)$ is the number such that $A(\alpha(n), \alpha(n)) = n$. In practice, $\alpha(n) \lt 5$ for any input less than about $^72$. So $O(\alpha(n))$ is basically $O(1)$. The difference only matters in theory, never really in practice. You'll find $O(\alpha(n))$ mostly when working with disjoint sets, ...

3

This approach suggest to pick any constant factor $k>1$ and use that whenever one needs to reallocate the array. That is, each time the array becomes full and has $n$ elements, a new array of size $k\cdot n$ is allocated, and data is copied from the old array. It is important here to multiply the size by a constant $k$ rather than, say, adding a fixed ...

3

Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$. It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about". For a specific example of this, look at matrix multiplication ...

2

The amortized cost per increment will be $O(1)$. In order to show it let's use the aggregate method. 0 - 000 1 - 001 2 - 002 3 - 010 4 - 011 5 - 012 6 - 020 7 - 021 8 - 022 9 - 100 10 - 101 11 - 102 12 - 110 13 - 111 14 - 112 15 - 120 ... We can notice that the bits in the 0th place are changing in every ...

2

The definition of $\Theta$ includes two constants that the function is multiplied with, and a smallest n where the relation applies. (There is an $n_0$ such that for all n ≥ $n_0$, $c_1 g(n) ≤ f(n) ≤ c_2 g(n)$). If $n < n_0$ then anything can happen. And if one algorithm comes with much smaller constants, then it may stay faster for some quite large n. ...

2

Ok so I think you can build a structure that has $O(1)$ (amortized) complexity for all operations, and using $O(n)$ space for $n$ insertions. The underlying array is a dynamic array (let's call it $T$) : it has amortized O(1) complexity for insertion at the end. In the array, you store tuples of values and booleans : the boolean will be set to false when ...

2

$\alpha(n)$ is the inverse Ackerman function.

1

The answer hinges on the definition of amortized cost. Since you haven't given such a definition, let me assume that you are using the common definition. Consider a data structure supporting operations $O_1,\ldots,O_m$. These operations have amortized cost $T_i$ (where $T_i$ could depend on parameters) if the total cost of a sequence of operations run ...

1

Your proposed answer contradicts itself, so no, it doesn't make sense. It starts by saying it will take $O(n \log n)$ time and concludes by saying it will take time $O(n \log n)^{1/4}$ time. You need to decide which you mean. And it's not clear where the $1/4$ came from.

1

If an operation, any operation, has an amortised cost of O(1), then performing it n times has cost O(n), by definition of “amortised cost”. Either your amortised cost is wrong, or your total cost is (assuming you change “O(n log n)” to “not O(n)”, to be a bit pedantic).

1

In the remove operation, every iteration of the while loop pops an element from stack_push, and this dominates the running time of remove. We can charge each such iteration to the insert operation which pushed the very same element to stack_push. This way we deduce that the amortized running time of both operations is $O(1)$. You can formalize the above ...

Only top voted, non community-wiki answers of a minimum length are eligible