1

I'm trying to understand this formula from this wikipedia article about amortized analysis.

In general if we consider an arbitrary number of pushes n + 1 to an array of size n, we notice that push operations take constant time except for the last one which takes $\Theta (n)$ time to perform the size doubling operation. Since there were n + 1 operations total we can take the average of this and find that pushing elements onto the dynamic array takes: $$ {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$$

For those who are not familiar with dynamic arrays and dynamic arrays in general, it does not matter in this case. I'm just giving some context about where the formula comes from but what I care about is the formula by itself.

Here's what I tried:

$${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}= \tfrac {n\Theta(1)}{n+1} + \tfrac {\Theta(n)}{n+1} = \tfrac {\Theta(n)\Theta(1)}{\Theta(n+1)} + \tfrac {\Theta(n)}{\Theta (n+1)} = \tfrac {\Theta(n)\Theta(1)}{\Theta(n)} + \tfrac {\Theta(n)}{\Theta (n)} = \Theta (1)$$

I don't know if it's correct to replace n+1 to $\Theta(n+1)$. If it is, could someone explain why, because it only came from my intuition.

Hugh
  • 129
  • I think it may be better to replace $\Theta(1)$ with some constant $c_1$ and $\Theta(n)$ with some constant $c_2$. Then, $$\dfrac{n\Theta(1) + \Theta(n)}{n + 1}\equiv\dfrac{c_1n + c_2n}{n + 1} = (c_1 + c_2)\dfrac{n}{n + 1}.$$ Now, when $n\to\infty$, $\dfrac{n}{n + 1}\to1$ and $(c_1 + c_2)\dfrac{n}{n + 1}\to(c_1 + c_2)\equiv\Theta(1)$.

    This is just me thinking out loud; let's see if someone has a better explanation!

     – an4s Jun 12 '20 at 17:35
  • Thanks for you answer. Why can we replace $\Theta(n)$ by a constant though? It depends of n – Hugh Jun 12 '20 at 17:39
  • Whoops! Sorry, I meant $c_2\cdot n$. – an4s Jun 12 '20 at 17:41

2 Answers2

3

Let me add explanation why we can change in expression $\frac{n\Theta (1)+\Theta (n)}{n+1}$ member $(n+1)$ to $\Theta(n):$

$\Theta(g)$ is set of functions $\left\lbrace f: \exists c_f,C_f>0, \ \exists N,\ n>N, c_fg \leqslant f \leqslant C_f g\right\rbrace$. We consider only non negative functions.

There are some properties outgoing from definition: $$f \cdot \Theta(g)=\Theta(g \cdot f)$$ $$\Theta(f) + \Theta(g)=\Theta(g + f)$$ And for $g>0$ holds $\frac{\Theta(f)}{g} = \Theta \left(\frac{f}{g}\right)$

Using these properties in mentioned fraction gives $$\frac{n\Theta (1)+\Theta (n)}{n+1}= \frac{\Theta (n)+\Theta (n)}{n+1} = \frac{\Theta (n)}{n+1}=\Theta \left( \frac{n}{n+1} \right)=\Theta(1)$$

Hugh
  • 129
zkutch
  • 13,410
  • Great answer. One thing is still bothering me. If $\Theta(g)$ is a set of function, what does it mean to multiply a set by a function? I've seen the equality in this case is is an abuse of notation, and ∈ would be more appropriated. Could $$f \cdot \Theta(g)=\Theta(g \cdot f)$$ be translated into $$f \cdot g ∈ \Theta(g \cdot f)$$ where g is whatever function f $$f ∈ \Theta(g)$$ ? – Hugh Jun 13 '20 at 00:45
  • 1
    @Hugues. Of course we need exact definition for $f \cdot \Theta(g)$ . We consider here $f$ as set with unique function, so as ${ f } \cdot \Theta(g)=\Theta(g \cdot f)$. All equality above are between sets i.e. works in both direction. For example in brought property equality mean ${ f } \cdot \Theta(g) \subset \Theta(g \cdot f)$ and reverse $\Theta(g \cdot f) \subset { f } \cdot \Theta(g)$. Many famous books suggests "one-way" understanding, but, I think, it's time to clear, that here is more interesting mathematical view. – zkutch Jun 13 '20 at 00:46
  • 1
    Comments have limit, so I continue here. Equality is abuse only in $f=O(g)$ case, which we understand, of course, as $f \in O(g)$, but almost everywhere in well known equalities, with type $O(f) = O(g)$, it is possible use mathematical "$=$" in its set notation understanding. – zkutch Jun 13 '20 at 00:55
  • It didn't come to my mind that f could be expressed as { f }. Things make a lot more sense now. I definitively think time / space complexity should be explained in a mathematical form instead of simple assessment such as "drop all constants". It does not cover all the cases and having a clear understanding of the signification of $\Theta$ should be the way to go. Thank you for the clarification and for your time, it really helped me. I'll try to write an article for fellow computer science students to explain things in a more mathematical way. – Hugh Jun 13 '20 at 01:05
  • 1
    Thanks for understanding. I am writing little notes in O-notation for my algorithms students, so my mind is "hot" now regards to it. I am and will be very glad, if can be useful for you and anybody other. – zkutch Jun 13 '20 at 01:12
1

The steps you've written are fine, but they are a bit opaque especially if you are not confident why you can take those steps. It is good for you to just write everything out explicitly using the definition of $\Theta(\cdot)$.

Let $p$ denote the constant time of a push operation, and let $g(n) \in \Theta(n)$ denote the time of the doubling operation, so that the amortized cost is $\frac{np + g(n)}{n+1}$. Explicitly, there exist positive constants $c,C$ such that $$cn \le g(n) \le Cn$$ for all sufficiently large $n$.

To show $\frac{np + g(n)}{n+1} \in \Theta(1)$, you want to find positive constants $c', C'$ such that $$c' \le \frac{np + g(n)}{n+1} \le C'$$ for sufficiently large $n$. This is simple if you just apply the definition of $g(n) \in \Theta(n)$ above.

$$c' := \frac{p+c}{2} \le \frac{np+cn}{n+1} \le \frac{np+g(n)}{n+1} \le \frac{np+Cn}{n+1} \le p+C =: C'.$$

angryavian
  • 89,882