# Questions tagged [mathematical-analysis]

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

101 questions
Filter by
Sorted by
Tagged with
9answers
85k 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 ...
4answers
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))$. ...
2answers
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 ...
1answer
527 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 ...
5answers
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 ...
2answers
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 ...
6answers
26k views

2answers
302 views

4answers
285 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 ...
1answer
813 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 ...
1answer
312 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)$ ?
2answers
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 ...
2answers
584 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 ...
3answers
571 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?
4answers
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 ...
3answers
447 views

0answers
807 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 ...
0answers
89 views

1answer
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 ...
1answer
383 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 ...
1answer
150 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 ...
1answer
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 ...
1answer
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 ...
1answer
420 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, ...
1answer
116 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 ...
0answers
79 views

### Maximizing the product of a set of dot products

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 ...
0answers
30 views

### The equation for how much data is produced every period [closed]

I am trying to find out how much data we produce to project how much we will produce in the future. I find stuff like this and this: There are 2.5 quintillion bytes of data created each day at our ...