# Questions tagged [mathematical-analysis]

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

100 questions
Filter by
Sorted by
Tagged with
838 views

### Why is the number of comparisons in a BST missing key lookup about 2 ln N?

In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1....
39 views

### Computing childrens of ith node of a d-ary tree

Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n). The formula for indices of children of node no. i is given as: {(1-i)d+2, ... , min{n,(1-i)d+d+1}...
50 views

41 views

### Algorithm for detecting a finite limit of time-series numbers

Is there a well known and proven algorithm to find the TOP (finite) limit of a set of points, which are time based metrics? I'm looking for an existing implementation, in order not to invent the wheel ...
84 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 ...
2k views

### What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph? [closed]

I've read many literature papers, but I still cannot understand their exact formalization definitions. Is their any difference among them or is there any relationship among them?
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 ...
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 ...
467 views

### Fixed point of hash

Are hashing algorithms constructed to guarantee that no fixed point exists? My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ...
82 views

### Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?
98 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 ...
363 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 ...
65 views

### Real RAM computational mode

Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
Disclaimer: I don't know much computational complexity theory. I am nevertheless curious. If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to ...
Suppose we have a 2-layer neural network completely connected with $d^{(0)}$ input units, $d^{(1)}$ hidden units and $d^{(2)}$ output units. We consider the error function given by \$J(w) = \frac{1}{2}\...