1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – an4s
    Jun 12, 2020 at 17:35
  • $\begingroup$ Thanks for you answer. Why can we replace $\Theta(n)$ by a constant though? It depends of n $\endgroup$
    – Hugh
    Jun 12, 2020 at 17:39
  • $\begingroup$ Whoops! Sorry, I meant $c_2\cdot n$. $\endgroup$
    – an4s
    Jun 12, 2020 at 17:41

2 Answers 2

3
$\begingroup$

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)$$

$\endgroup$
5
  • $\begingroup$ 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)$$ ? $\endgroup$
    – Hugh
    Jun 13, 2020 at 0:45
  • 1
    $\begingroup$ @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. $\endgroup$
    – zkutch
    Jun 13, 2020 at 0:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – zkutch
    Jun 13, 2020 at 0:55
  • $\begingroup$ 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. $\endgroup$
    – Hugh
    Jun 13, 2020 at 1:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – zkutch
    Jun 13, 2020 at 1:12
1
$\begingroup$

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'.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .