# Questions tagged [mathematical-analysis]

Questions related to mathematical analysis (often called analysis by mathematicians)

100 questions
Filter by
Sorted by
Tagged with
86k views

### How/when is calculus used in Computer Science?

Many computer science programs require two or three calculus classes. I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus ...
4k views

### What is the meaning of $O(m+n)$?

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
9k views

### Changing variables in recurrence relations

Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations. The following method can be illustrated with this ...
528 views

### Proving the (in)tractability of this Nth prime recurrence

As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
4k views

### Are the functions always asymptotically comparable?

When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the ...
17k views

### Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
27k views

302 views

287 views

### What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
816 views

### Master theorem and constants independent of $n$

I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version): $$T(n)=4T(n/2)+O(r)$$ $r$ is independent of $n$. Case 1 of the Master theorem applies ...
315 views

### what is the complexity of recurrence relation?

what is the complexity of below relation $T(n) = 2*T(\sqrt n) + \log n$ and $T(2) = 1$ Is it $\Theta (\log n * \log \log n)$ ?
1k views

### Is Big-Oh notation preserved under monotonic functions?

I was just looking at the big-Oh notation. I wanted to know if the following is true in general $$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$ I can prove that this is true if $g$ is ...
585 views

### Mathematics Courses for Computer Scientists [closed]

I am looking for standard math courses (Calculus 1, Calculus 2, Linear Algebra, etc.) that were developed specifically for computer scientists, and use computer-science examples for motivation. For ...
574 views

### How to prove $(n+1)! = O(2^{(2^n)})$

I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives. Can anyone tell me how i can prove this?
9k views

### Trigonometry in computer science

What's the use of studying trigonometry in computer science? I mean, is it essential? Does it have a specific application in computer science? Because I can't seem to muster enough motivation for ...
447 views

886 views

### Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code

I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial ...
91 views

48 views

### Can most programs (except the IO part) be re-written as a sequence of matrix operations?

I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
405 views

### Set of all rational numbers less than given computable real number is decidable

Prove that set of rational numbers less than given computable real number is decidable This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another ...
153 views

### Error in Generating Function Solution

I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books ...
101 views

### Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...
159 views

### Reference request: Introduction to reinforcement learning with hand calculation examples

For me, the most difficulty when it comes to learning about reinforcement learning is that there is not much to learn in the sense that without running some algorithm, it is very difficult to get a ...
427 views

### Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, ...
118 views

### Upper bound on the number of triangles in a planar graph

For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller ...
So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following: $\prod_{x \in X} b \cdot x$ where the components of $b$ sum to $1$ If it matters the components of ...