Timeline for Confusion about the definition of the average-case running time of algorithms
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2021 at 18:18 | comment | added | Yuval Filmus | Both are random variables. If you take a random variable and pass it through a function, you get another random variable. | |
| Jul 24, 2021 at 17:49 | comment | added | Emad | @YuvalFilmus So $X$ is a random variable? Or $T(X)$ is? There should be some random variable. | |
| Jul 24, 2021 at 17:41 | comment | added | Yuval Filmus | It stands for the running time of the algorithm on the input $X$. | |
| Jul 24, 2021 at 17:14 | comment | added | Emad | @YuvalFilmus Can you please explain in the definition of average-case time complexity what the expression on the right means? I know it's the mathematical expectation of some random variable but what is that variable? what does $T(X)$ mean? | |
| Mar 28, 2017 at 12:18 | vote | accept | hengxin | ||
| Mar 28, 2017 at 12:17 | comment | added | Yuval Filmus | Right, that's exactly what is happening there. | |
| Mar 28, 2017 at 12:16 | comment | added | hengxin | I think the equality $$ \newcommand{\Tavg}{T_{\mathit{avg}}} \newcommand{\EE}{\mathbb{E}} \Tavg(n) = \sideset{\EE}{}{}_{X \sim \mu_n} [T(X)] = \sum_{i=0}^{n-1} \Pr[I=i] \EE[T(X)|I=i] $$ solves my confusion. It is "computing expectation by conditioning". Isn't it? Thanks. | |
| Mar 28, 2017 at 11:50 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 398 characters in body
|
| Mar 28, 2017 at 11:45 | comment | added | Yuval Filmus | This formula is true but unhelpful. I'll update my answer with some more information. | |
| Mar 28, 2017 at 11:40 | comment | added | hengxin | Thanks. However, I am still confused about the definitions. According to $T_{avg}(n) = E_{X \sim \mu_{n}} [T(X)]$, I would expect $T_{avg}(n) = \frac{1}{n!} \sum_{X \in U_n}T(X)$ given that $\mu_{n}$ is chosen as the uniform distribution over $U_{n}$, the set of all possible permutations. What is wrong here? | |
| Mar 28, 2017 at 10:19 | history | answered | Yuval Filmus | CC BY-SA 3.0 |