Questions related to mathematical analysis (often called analysis by mathematicians)
1
vote
1answer
39 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
0answers
44 views
A few questions on Difference of Gaussians [closed]
I use this formula for Difference of Gaussians (DoG): $\frac{1}{\sigma}(\frac{x^2}{2\sigma^2}-1.0)e^{\frac{-x^2}{2\sigma^2}}$
What is the relationship between this formula and the difference of two ...
0
votes
1answer
110 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 ...
1
vote
2answers
348 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 ...
3
votes
3answers
212 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?
6
votes
2answers
618 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
260 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
24 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.
...
3
votes
1answer
254 views
Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using Master Method
Introduction to algorithms, 3rd edition has an example of how to solve therecurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying Master Theorem, p.95
I am very ...
3
votes
1answer
286 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
174 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)) = \{ ...
8
votes
6answers
584 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 ...
5
votes
1answer
165 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)$ ?
1
vote
1answer
90 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 ...
8
votes
2answers
186 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 ...
5
votes
3answers
219 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) = ...
23
votes
2answers
542 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
176 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{, ...
7
votes
0answers
126 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\\
...
10
votes
0answers
266 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 ...
8
votes
4answers
251 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
169 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 ...
4
votes
1answer
155 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 ...
5
votes
2answers
172 views
Solving Recurrence Relations 'Chip & Conquer'
I've been tasked with solving some recurrence relations, and I've been running into trouble with so called 'chip & conquer' relations.
Here are some example problems:
$$T(n) = T(n-5) + cn^2$$
...
6
votes
2answers
174 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 ...
8
votes
2answers
313 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 ...
