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

learn more… | top users | synonyms

2
votes
2answers
100 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 ...
2
votes
2answers
275 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
316 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
80 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 ...
1
vote
0answers
26 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
122 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
209 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
63 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
49 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
154 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
2k 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
327 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?
7
votes
2answers
3k 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
323 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
37 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
876 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 ...
5
votes
1answer
1k 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
234 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)) = \{ ...
9
votes
6answers
3k 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
221 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
103 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 ...
9
votes
2answers
213 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
347 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) = ...
27
votes
2answers
998 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
575 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
175 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\\ ...
14
votes
1answer
429 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
445 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
260 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
300 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
367 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$$ ...
7
votes
2answers
271 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 ...
10
votes
2answers
367 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 ...