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

learn more… | top users | synonyms

2
votes
1answer
87 views

How to calculate an accurate estimated reading time of text?

I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the ...
74
votes
9answers
13k 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 ...
9
votes
2answers
89 views

Decidability of checking an antiderivative?

Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether $$F(x) = \int G(x)dx.$$ Let's suppose that my functions are composed of elementary functions (polynomials, ...
2
votes
1answer
37 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 ...
3
votes
0answers
62 views

Complexity for finding zeroes of sum of cosines

Consider the following equation with variable $n \in \mathbb{N}$: $$\sum \limits_{i=1}^{k} \cos(n\theta_{i}) = 0.$$ Given $\theta_1,\dots,\theta_k$, I'd like to determine whether there exists $n \in ...
1
vote
1answer
62 views

Amortized analysis for doubling resizing array is ~3n

I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused: Question 2: What if instead we decide to double the size of ...
3
votes
0answers
31 views

A totally-ordered set of functions

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
0
votes
1answer
51 views

Looking for an algorithm to generate an identicon/avatar from genome data

I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form. Identicons are essentially a visual hash of of data. usually string data ...
3
votes
2answers
224 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 ...
3
votes
3answers
1k views

Why do Computers use Hex Number System at assembly language?

Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? ...
6
votes
2answers
390 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 ...
0
votes
1answer
163 views

Problem with derivative of sigmoid activation function

I'm following Jeff heatons book 'Introduction to Neural Networks with Java'. To get node deltas, we need to calculate $f'(sum)$. In the very first row for Training Element #1, we need to compute $f'(1....
1
vote
0answers
29 views

Is the moment generating function for a sequence $\{a_n\}$ unique? [closed]

Suppose $\{a_n\}$ is a sequence with moment generating function $A(z)=\sum_{k \ge 0} a_kz^k$. Can a sequence $\{b_n\}$ with $b_n \neq a_n$ for at least one $n\in \mathbb N$ have the same moment ...
3
votes
2answers
135 views

What does it mean to multiply or divide polynomials?

What does it mean to multiply or divide polynomials? I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical ...
8
votes
1answer
240 views

High maths for game theory

I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky. But I find it hard to understand the ...
3
votes
1answer
73 views

How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $

I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where $d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $. I am a statistician ...
1
vote
2answers
51 views

Looking for Rating Functions

I'm looking for something i would call rating functions. I'm searching for some literature about this concept. I'm not really sure about the terminology, but what I mean should be pretty obvious. A ...
0
votes
1answer
191 views

Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?

I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09). Although you guys don't have to go and look at the video, I feel that the ...
5
votes
4answers
3k 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 ...
5
votes
3answers
370 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?
9
votes
2answers
6k 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 ...
8
votes
1answer
390 views

Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?

The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS. ...
0
votes
3answers
47 views

Heuristically determine a value f such that a probability d/f approaches 1/2

We have a set X of N elements. We want to get a new set X' having a size M < N. ...
5
votes
1answer
2k views

Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
11
votes
2answers
3k 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 ...
1
vote
3answers
277 views

Value of constants in Big Theta notation

In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$? Definition: $\qquad \displaystyle \Theta (g(n)) = \{ f(n)...
11
votes
6answers
6k views

n*log n and n/log n against polynomial running time

I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\...
6
votes
1answer
238 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)$ ?
2
votes
1answer
117 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 ...
10
votes
2answers
222 views

Is $O$ contained in $\Theta$?

So I have this question to prove a statement: $O(n)\subset\Theta(n)$... I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\...
5
votes
3answers
404 views

Asymptotic growth rate of $f(n)$ and $f(n+1)$

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds: $\qquad f(n+1) = \...
33
votes
2answers
2k 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))$. ...
2
votes
2answers
1k views

Function Maximization in Java

I have a bivariate function like $ f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y} $ and I want to find its global maximum over a range of $ x \in [0, 200] \text{, ...
8
votes
0answers
206 views

Complexity of computer algebra for systems of trigonometric equations

As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence: $\qquad f_{p_0} = 0\\ \...
15
votes
1answer
452 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 ...
12
votes
4answers
832 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 ...
1
vote
1answer
293 views

Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...
5
votes
1answer
418 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 ...
7
votes
2answers
321 views

$\log^*(n)$ runtime analysis

So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$. I'm trying to solve the following: is $\log^*(2^{2^n})$ little $o$, little $\omega$...
11
votes
2answers
413 views

How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?

This a homework question from Udi Manber's book. Any hint would be nice :) I must show that: $n(\log_3(n))^5 = O(n^{1.2})$ I tried using Theorem 3.1 of book: $f(n)^c = O(a^{f(n)})$ (for $c &...