<p>Real Analysis is very important to certain branches of computer science. I am assuming you know the epsilon-delta definition of the limit of a function, but I would argue that the heart of limits and real analysis is sequences. In fact, the following definition is equivalent to the epsilon-delta definition:</p>
<blockquote>
<p>Let <span class="math-container">$f:\mathbb{R}\to\mathbb{R}$</span> be a real function. Let <span class="math-container">$a, L \in\mathbb{R}$</span>. We say the <em>limit of <span class="math-container">$f(x)$</span> as <span class="math-container">$x$</span> approaches <span class="math-container">$a$</span></em>, denoted <span class="math-container">$\lim_{x\to a} f(x)$</span> equals <span class="math-container">$L$</span> if for every sequence <span class="math-container">$(x_n)_{n\in\mathbb{N}}$</span> such that <span class="math-container">$x_n \to a$</span> the sequence <span class="math-container">$\big(f(x_n)\big)_{n\in\mathbb{N}}$</span> satisfies <span class="math-container">$f(x_n) \to L$</span>.</p>
</blockquote>
<p>Thus if you are analyzing a function that computes or optimizes a function by producing sequences of points, you need real analysis. Also real analysis is used in the proof of the Universal Approximation Theorem in Machine Learning.</p>

CC BY-SA 4.0
2024-02-26T15:22:07.440Z
2024-02-26T15:22:07.440Z
NaturalLogZ
<p>[This is only partly an answer but way too long for a comment]</p>
<p>Real analysis is definitely relevant for computer science! It gets used all over the place in scientific computing. Take a look at any Numerical Analysis book. Concepts covered in real analysis like compactness and continuity showing up in computability theory (e.g. Turing reductions correspond to Turing functionals on Cantor space, which are continuous functions) and in the construction of oracles in complexity theory (lookup &quot;generic oracles&quot; e.g. <a href="https://doi.org/10.1016/S0890-5401(03)00018-X" rel="noreferrer">An oracle builder's toolkit</a>).</p>
<p>(&quot;Analysis&quot; in general is even more widely useful, but since your Q is specifically about a Real Analysis class I will stick to that. Just some mentions: differential equations can be used to derive phase transitions in combinatorial settings such as random graphs, SAT algorithms, clique algorithms, etc. Complex analysis can be used to estimate growth rates as in the generating function approach to bounding recurrence relations in algorithms. And it shows up a lot in things like the Unique Games Conjecture, hardness of approximation, and metric embedding.)</p>
<p>That said, I don't think Real Analysis is a valid &quot;substitute&quot; for Algorithms from the point of view of a CS degree. The point of an Algorithms class is not just to have another mathematically formal/rigorous course in the CS curriculum. The point is that algorithms are a <em>core part of computer science</em> (maybe even &quot;the core&quot;, but I don't want to quibble). Perhaps unfortunately given your question, I do think that the same cannot be said for Real Analysis, however useful it might be in certain parts of CS.</p>
<p>Personally: if I saw a CS Theory grad school applicant was <em>missing</em> an Algorithms class from their transcript, that would be a big question mark that needed some explaining. e.g. I'd want a really good answer to the question &quot;How do you know you want to do TheoryCS if you haven't even taken an algorithms class?&quot; (There can be good answers to that question! But it's a risk.)</p>
<p>If you think you can self-learn the Algorithms material so easily, can you propose testing out of the class? That would hopefully satisfy your department's requirement, still let you have it on your transcript, but hopefully take much less time than actually taking the class. (Unfortunately it is unlikely to help tuition-wise, as schools tend to be sticklers about &quot;if it's on your transcript someone must have paid tuition for it&quot;.)</p>

CC BY-SA 4.0
2024-04-06T11:47:19.230Z
Interesting, when I am judging applications for a CS Theory grad school, I am looking for math classes. It doesn't matter which. A CS grad student can learn algorithms by being a TA, but that would be much harder for Real Analysis.
Jakub Opršal
CC BY-SA 4.0
2024-04-06T14:33:32.380Z
@JakubOpršal I also look for math classes. But, as I said, if a student hasn't taken algorithms (or, say, theory of computation) how do they know they want to do Theory?
Joshua Grochow
CC BY-SA 4.0
2024-02-28T18:03:11.407Z
2024-02-28T18:03:11.407Z
Joshua Grochow
<p>I'm a recent Math major who switched to a double major with Computer Science.</p>
<p>I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data Structures &amp; Algorithms, and from a cursory read of the Algorithms textbook, it seems to be something I could learn on my own time in lieu of classroom instruction. Not only that, financial aid can only finance so many courses before it dips into my pocket.</p>
<p>I'm really interested in taking Real Analysis ; it is the bedrock course for any mathematical sciences. However, Real Analysis concerns topics such as limits and continuity, whereas Algorithms (except for a few cases) deals with computations in the realm of finite, discrete intervals.</p>
<p>Thus, I'm taking a pause and asking TCS: is my intention of taking Real Analysis in place of Algorithms short-sighted? The only justifications I can think of is</p>
<ol>
<li>Real Analysis is a core course for anyone thinking of doing mathematical sciences, especially for graduate school.</li>
<li>Real Analysis is a staple of graduate-level Computer Science.</li>
</ol>
<p>Basically; what is the point of Real Analysis for Computer Science? It doesn't seem to hold much value for a academic field concerned with computations in the discrete.</p>
<p>Thank you for your responses.</p>
<p>Edit; Due to the one of the responses by Clement, I should elaborate. Real Analysis presents a challenge to me in terms of self teaching. I would rather not develop faulty tricks and methods to understand what i am learning. I rather study under the guide of a math professor who knows what they are doing, and I can reach out to when facing difficulty in comprehension of the material. Algorithms does not seem to present as big a challenge.</p>

CC BY-SA 4.0
2024-02-24T03:09:57.797Z
Not quite what you're asking, but I'm curious here. What is the part of the argument for "I could learn [algorithms] on my own time" that does not apply to real analysis? Isn't the premise of that statement (for both) that the lectures, assignments, office hours, etc. provide nothing the textbook does not already offer?
Clement C.
CC BY-SA 4.0
2024-02-24T22:27:26.917Z
@ClementC. This is a strong argument that has not occurred to me prior. Thinking of it now, Real Analysis is very imposing in a way that Algorithms does not seem to be. Due to that, I rather be instructed by a mathematician who knows what they are talking about rather then self-teach and possibly fall into faulty methods of understanding. Algorithms just doesn't seem to be that complex to understand in comparison.
wonderinghuh
CC BY-SA 4.0
2024-02-26T16:17:43.507Z
Two Qs: 1) What is the difference at your school between "Data Structures & Algorithms" vs "Algorithms"? And 2) What do you want to do with these things afterwards? (Learning-wise, career-wise, etc.) Both Qs have bearing on my potential answer.
Joshua Grochow
CC BY-SA 4.0
2024-02-26T19:44:00.613Z
Sometimes continuous models are easier / more amenable to solve computationally. Example: https://en.m.wikipedia.org/wiki/Linear_programming_relaxation -> the continuous solution is then an approximate solution for the discrete problem (ORLY!). Best to be knowledgeable in both worlds.
Hermann Gruber
CC BY-SA 4.0
2024-02-27T18:24:08.233Z
Many algorithms for optimization and sampling are based on discretizations of continuous processes. From this perspective, convergence of these continuous processes are necessary for convergence of the discretized processes. Insights from analysis can help design better continuous processes and discretizations.
Holden Lee
CC BY-SA 4.0
2024-02-28T01:14:45.903Z
@JoshuaGrochow DS&A mostly covers DS with a intro section into algorithms. Algorithms is the fully-fleshed out lectures on well, algorithms. Career wise, industry then grad-school.
wonderinghuh
CC BY-SA 4.0
2024-03-05T02:47:16.500Z
Computability and Complexity in Analysis is also an active area of research. E.g. what is the complexity of computing the integration of a poly-time computable real function?
Kaveh
CC BY-SA 4.0
2024-03-05T02:48:10.390Z
Numerical Analysis is also an important area of CS, and it's what many numerical methods are based on.
Kaveh
CC BY-SA 4.0
2024-03-05T02:49:30.183Z
Finally, real and functional analysis are important in optimization theory and machine learning where you need to think about the space of real functions represented by a NN and how they behave, or differentiation used in backprop algorithm.
Kaveh
CC BY-SA 4.0
2024-03-05T02:52:43.390Z
One more: the area of Boolean function analysis uses a lot of methods from analysis.
Kaveh
<ds.data-structures><analysis-of-algorithms>
What is the relevance of Real Analysis in TCS?
wonderinghuh
# What is the relevance of Real Analysis in TCS?

(Asked by: username_0 on 2024-02-23)

I'm a recent Math major who switched to a double major with Computer Science.

I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data Structures & Algorithms, and from a cursory read of the Algorithms textbook, it seems to be something I could learn on my own time in lieu of classroom instruction. Not only that, financial aid can only finance so many courses before it dips into my pocket.

I'm really interested in taking Real Analysis ; it is the bedrock course for any mathematical sciences. However, Real Analysis concerns topics such as limits and continuity, whereas Algorithms (except for a few cases) deals with computations in the realm of finite, discrete intervals.

Thus, I'm taking a pause and asking TCS: is my intention of taking Real Analysis in place of Algorithms short-sighted? The only justifications I can think of is

1. Real Analysis is a core course for anyone thinking of doing mathematical sciences, especially for graduate school.
2. Real Analysis is a staple of graduate-level Computer Science.

Basically; what is the point of Real Analysis for Computer Science? It doesn't seem to hold much value for a academic field concerned with computations in the discrete.

Thank you for your responses.

Edit; Due to the one of the responses by Clement, I should elaborate. Real Analysis presents a challenge to me in terms of self teaching. I would rather not develop faulty tricks and methods to understand what i am learning. I rather study under the guide of a math professor who knows what they are doing, and I can reach out to when facing difficulty in comprehension of the material. Algorithms does not seem to present as big a challenge.

**Tags:** ds.data-structures, analysis-of-algorithms

> **Comments:**
> **username_1**: Not quite what you're asking, but I'm curious here. What is the part of the argument for "I could learn [algorithms] on my own time" that does not apply to real analysis? Isn't the premise of that statement (for both) that the lectures, assignments, office hours, etc. provide nothing the textbook does not already offer?  
> **username_0**: @ClementC. This is a strong argument that has not occurred to me prior. Thinking of it now, Real Analysis is very imposing in a way that Algorithms does not seem to be. Due to that, I rather be instructed by a mathematician who knows what they are talking about rather then self-teach and possibly fall into faulty methods of understanding. Algorithms just doesn't seem to be that complex to understand in comparison.  
> **username_2**: Two Qs: 1) What is the difference at your school between "Data Structures & Algorithms" vs "Algorithms"? And 2) What do you want to do with these things afterwards? (Learning-wise, career-wise, etc.) Both Qs have bearing on my potential answer.  
> **username_3**: Sometimes continuous models are easier / more amenable to solve computationally. Example: https://en.m.wikipedia.org/wiki/Linear_programming_relaxation -> the continuous solution is then an approximate solution for the discrete problem (ORLY!). Best to be knowledgeable in both worlds.  
> **username_4**: Many algorithms for optimization and sampling are based on discretizations of continuous processes. From this perspective, convergence of these continuous processes are necessary for convergence of the discretized processes. Insights from analysis can help design better continuous processes and discretizations.  
> **username_0**: @JoshuaGrochow DS&A mostly covers DS with a intro section into algorithms. Algorithms is the fully-fleshed out lectures on well, algorithms. Career wise, industry then grad-school.  
> **username_5**: Computability and Complexity in Analysis is also an active area of research. E.g. what is the complexity of computing the integration of a poly-time computable real function?  
> **username_5**: Numerical Analysis is also an important area of CS, and it's what many numerical methods are based on.  
> **username_5**: Finally, real and functional analysis are important in optimization theory and machine learning where you need to think about the space of real functions represented by a NN and how they behave, or differentiation used in backprop algorithm.  
> **username_5**: One more: the area of Boolean function analysis uses a lot of methods from analysis.  

---

## 2 answers

### Answer by username_2 on 2024-02-28. Score: 6 | Accepted answer

[This is only partly an answer but way too long for a comment]

Real analysis is definitely relevant for computer science! It gets used all over the place in scientific computing. Take a look at any Numerical Analysis book. Concepts covered in real analysis like compactness and continuity showing up in computability theory (e.g. Turing reductions correspond to Turing functionals on Cantor space, which are continuous functions) and in the construction of oracles in complexity theory (lookup "generic oracles" e.g. [An oracle builder's toolkit](https://doi.org/10.1016/S0890-5401(03)00018-X)).

("Analysis" in general is even more widely useful, but since your Q is specifically about a Real Analysis class I will stick to that. Just some mentions: differential equations can be used to derive phase transitions in combinatorial settings such as random graphs, SAT algorithms, clique algorithms, etc. Complex analysis can be used to estimate growth rates as in the generating function approach to bounding recurrence relations in algorithms. And it shows up a lot in things like the Unique Games Conjecture, hardness of approximation, and metric embedding.)

That said, I don't think Real Analysis is a valid "substitute" for Algorithms from the point of view of a CS degree. The point of an Algorithms class is not just to have another mathematically formal/rigorous course in the CS curriculum. The point is that algorithms are a *core part of computer science* (maybe even "the core", but I don't want to quibble). Perhaps unfortunately given your question, I do think that the same cannot be said for Real Analysis, however useful it might be in certain parts of CS.

Personally: if I saw a CS Theory grad school applicant was *missing* an Algorithms class from their transcript, that would be a big question mark that needed some explaining. e.g. I'd want a really good answer to the question "How do you know you want to do TheoryCS if you haven't even taken an algorithms class?" (There can be good answers to that question! But it's a risk.)

If you think you can self-learn the Algorithms material so easily, can you propose testing out of the class? That would hopefully satisfy your department's requirement, still let you have it on your transcript, but hopefully take much less time than actually taking the class. (Unfortunately it is unlikely to help tuition-wise, as schools tend to be sticklers about "if it's on your transcript someone must have paid tuition for it".)

> **Comments:**
> **username_7**: Interesting, when I am judging applications for a CS Theory grad school, I am looking for math classes. It doesn't matter which. A CS grad student can learn algorithms by being a TA, but that would be much harder for Real Analysis.  
> **username_2**: @JakubOpršal I also look for math classes. But, as I said, if a student hasn't taken algorithms (or, say, theory of computation) how do they know they want to do Theory?  

---

### Answer by username_6 on 2024-02-26. Score: 1

Real Analysis is very important to certain branches of computer science. I am assuming you know the epsilon-delta definition of the limit of a function, but I would argue that the heart of limits and real analysis is sequences. In fact, the following definition is equivalent to the epsilon-delta definition:

> Let $f:\mathbb{R}\to\mathbb{R}$ be a real function. Let $a, L \in\mathbb{R}$. We say the *limit of $f(x)$ as $x$ approaches $a$*, denoted $\lim\_{x\to a} f(x)$ equals $L$ if for every sequence $(x\_n)\_{n\in\mathbb{N}}$ such that $x\_n \to a$ the sequence $\big(f(x\_n)\big)\_{n\in\mathbb{N}}$ satisfies $f(x\_n) \to L$.

Thus if you are analyzing a function that computes or optimizes a function by producing sequences of points, you need real analysis. Also real analysis is used in the proof of the Universal Approximation Theorem in Machine Learning.


---

