1
vote
3answers
30 views

Nth value of Function

Given x and y we define a function as follow : f(1)=x f(2)=y f(i)=f(i-1) + f(i+1) for i>2 Now given x and y, how to calculate f(n) Example : If x=2 and y=3 ...
0
votes
0answers
12 views

How to normalise logarithm depending on the size of the range of possible values

I'm attempting to write a function which can be used to generate weighted random numbers between a set range, the size of which can arbitrarily grow and shrink, depending on some modifying value to ...
0
votes
0answers
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
0
votes
0answers
84 views

Function acting on a graph

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows: Given a graph $G= \langle V_G, E_G ...
0
votes
1answer
31 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
0
votes
1answer
26 views

asymptotic analysis

For each of the following sentences involving functions f and/or g, find a counterexample to show that it is false: What is meant by counterexamples?
2
votes
0answers
33 views

Decide whether a function has an elementary indefinite integral without determining it!

Risch, who developed the algorithm in 1968, called it a decision procedure, because it is a method for deciding whether a function has an elementary function as an indefinite integral; and also, if ...
1
vote
3answers
149 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
0
votes
1answer
78 views

Generating Random Serialnumber with least similarity

I want to generate 16-digits hexadecimal serial-number like: F204-8BE2-17A2-CFF3. (This pattern give me 16^16 distinct serial-number But I don't need all of them as I describe below) I need an idea ...
-2
votes
1answer
64 views

How to change RSA Algorithm to be able to calculate D based on E or reverse?

I need an algorithm like RSA (http://en.wikipedia.org/wiki/RSA_(algorithm)) with an infrastructural different. RSA is a works very nice, it uses Euler's Phi function to calculate 2 values that are ...
0
votes
1answer
41 views

Scoring algorithm for a Game

I have three variables: Good points = You get 1 good point every time you get a question correct. The maximum good points you can obtain is 21. Bad points = You get 1 bad point every time you ...
0
votes
1answer
19 views

compute an order value for an array of arrays

I am trying to find a solution to the following problem. I am not a mathematicians so my language might need some improvements, but here it is. I have $n$ groups of numbers. Each Group of numbers ...
0
votes
1answer
68 views

What is the Mirror/PingPong clamp mode algorithm?

I do programming as a hobby, and in a dynamic system various numerical values inevitably change. Those values can be greater than or less than the expected range, in which case they need to be ...
1
vote
2answers
127 views

How can I optimise the power series calculation of the exponential function?

In an answer to the question Fastest way to calculate $e^x$ upto arbitrary number of decimals? there is a description of a method by which the number of terms needed to calcluate $e^x$ to a given ...
0
votes
2answers
342 views

How do I prove that a function grows faster than another? [closed]

I need to prove that one function, say $n$ grows faster than say, $\sqrt{n}$?
1
vote
2answers
505 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
52 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
1
vote
1answer
45 views

Algorithm to find the rotational degrees of a point according to some function

Hi I'm developing a game. In this game you can fire a missile, the path of the missile is given accord some function. For example if the function is f(x)=x^2 the missile should look like this. Is ...
3
votes
5answers
223 views

How to generate unique id from each element in matrix?

I'm coming from the programming world , and I need to create unique number for each element in a matrix. Say I have a $4\times4$ matrix $A$. I want to find a simple formula that will give each of the ...
2
votes
2answers
56 views

One-to-one functions between vectors of integers and integers, with easily computable inverses

I'm trying to find functions that fit certain criteria. I'm not sure if such functions even exist. The function I'm trying to find would take vectors of arbitrary integers for the input and would ...
1
vote
1answer
60 views

Fourier transformations in Simon's quantum paper

I am reading this paper by Simon. This is one of the earliest quantum algorithm papers. In the paper he presents a routine starting at the end of page six. The first step runs a Fourier transformation ...
1
vote
3answers
169 views

Help with Big O and Big Omega problem.

this is a homework problem: 1) $$ \text{Let }f(n) = n^2+5000 \text{ and } g(n) = 5(n^2) + 100.\text{ Prove formally that }f(n) = \theta (g(n)) $$ My attempt: a)Prove f(n) is $ O(g(n)) $: When $ n ...
0
votes
1answer
51 views

What is the complexity (\Theta version) of the function $\sum = 3i^{\frac{3}{2}}$

What is the complexity ($\Theta$ version) of the function $$\sum\limits_{i=1}^n 3i^{\frac 3 2}$$ I think that it is just $\Theta(n^3)$ because the $n^3$ grows faster then the constant or the square ...
0
votes
0answers
69 views

backward stability of full svd decomposition

Why is it impossible for the full SVD decomposition of a matrix A to be a backward stable algorithm? This was mentioned in one of my readings but it doesn't explain why.
0
votes
2answers
59 views

How can we denote the following function in terms of big-O notation?

I have got a function and want to denote it in terms of bigO notation. f(n) = log4n+n*(1/3). Is this function O(n)? (* here is the multiplication) Thanks for your help
1
vote
2answers
43 views

The growth rate of the functions with respect to each other

There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$? Thank you.
2
votes
1answer
118 views

Reconstructing a Paragraph From Random Set of Words

Goal: Take a collection of randomly shuffled words that represent x and y coordinates on a plane, re-order them such to construct the original paragraph those words came from. Each word represents ...
2
votes
2answers
46 views

Is there a general algorithm that can be implemented via a computer program that can identify the function being represented by a graph?

It might help understanding my question to think of the hypothetical situation in which I draw a seemingly random function on a piece of paper (with an accurate coordinate axis already on the paper), ...
1
vote
0answers
17 views

Need help transforming an list of numbers into some uniform list in order to apply the rule mentioned inside more effectively

So I have a list of values like so L1 = [-4 -3 5 8 ]; Note the sum of each element in L1 will always be > 0. The operation I am performing on L1 is as follows ...
0
votes
3answers
75 views

how to calculate an integer x let x^2+2mx-n is a square number?

Let m, n be positive integers. Let $x^2+2mx-n=p^2$ for some p which is a positive integer. How does one solve for x? Sorry forgot this: x must be an integer.
3
votes
1answer
1k views

Recurrences that cannot be solved by the master theorem

I am given this problem as extra credit in my class: Propose TWO example recurrences that CANNOT be solved by the Master Theorem. Note that your examples must follow the shape that $T(n) = ...
2
votes
1answer
164 views

Compute index from 2d array to find correspondent index in a flat array

I am a programmer (not a mathematicians), and I am encountering a problem in my software which, if possibly solved mathematically would save a lot of performance issues. I have an array of arrays ...
2
votes
3answers
330 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
1
vote
2answers
149 views

Random Sequence Generator function

I want to find out a function or algorithm, whichever is suitable, which can provide me a random sequence. Like Input: 3 Output: {1,2,3} or {1,3,2} or {2,1,3} or {2,3,1} or {3,1,3} or {3,2,1} Same ...
5
votes
1answer
120 views

What function $f$ such that $a_1 \oplus\, \cdots\,\oplus a_n = 0$ implies $f(a_1) \oplus\, \cdots\,\oplus f(a_n) \neq 0$

For a certain algorithm, I need a function $f$ on integers such that $a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$ (where the ...
-4
votes
2answers
407 views

How do I turn this piecewise function into a “normal” function?

I am a Java developer building a web app that I will be deploying "in the cloud" (I hate that expression) in a few months. I'm trying to develop a function that will let me spawn and kill the right ...
1
vote
5answers
237 views

Any fastest algorithm for $f(n) = f(n-1) \cdot f(n-2)$ where $3 \leq n \leq 1000000$

Any fastest algorithm for $$ f(n) = f(n-1)\cdot f(n-2)\quad\text{ where }\quad f(1) = 1,\quad f(2) = 2 $$ for $3 \leq n \leq 1000000 $.
0
votes
1answer
51 views

Algorithms and generalisation of functions

I admit I'm little bit poor in functions in mathematics. But I'm in real urge to get this riddle out. How to express $$x(n)=x(n-1)+x(n-2)+1,$$ where $n>1$ and $x(0)=0$ and $x(1)=1$, in terms of ...
1
vote
2answers
165 views

Function that magnifies small changes and compresses large changes

I need a function (for a heatmap algorithm) that takes a percentage difference between two values, and returns a number between 0 and 1. The output will be used in coloring parts of the screen. The ...
1
vote
1answer
40 views

Formula to scale a series that is being bent with a root / power.

I have a reference number, Rx, and a series of numbers, Sx[], to compare to it. Let's call the output Ox[]. I am using a simple square root to accelerate the apparent difference between the reference ...
2
votes
1answer
137 views

Algorithms for deciding whether a function over a finite ring is polynomial or not?

Let $R$ be a finite ring, and $f$ be a function from $R$ to $R.$ Suppose I want to know whether $f$ can be represented as a polynomial or not? Are there any good algorithms for finding this out?
2
votes
3answers
625 views

calculating unique value from given numbers

let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, ...
2
votes
1answer
282 views

Perfect Hash Function just an Injection?

I just read up on the concept of perfect hash functions on a set $S$. I am quoting: "A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with ...
4
votes
3answers
774 views

non time constructible functions

A function $T: \mathbb N \rightarrow \mathbb N$ is time constructible if $T(n) \geq n$ and there is a $TM$ $M$ that computes the function $x \mapsto \llcorner T(\vert x\vert) \lrcorner$ in ...
2
votes
1answer
204 views

Function for base-stock level

This problem is work related not school related. I am developing a simple inventory management system to solve a digital supply chain problem and I need help with an algorithm to control the ...
0
votes
2answers
619 views

Specific fitness function for genetic algorithm

I have a program that assign students to different courses using a genetic algorithm. To get the best assignation I have a fitness function that evaluates the distribution of the students and their ...
0
votes
2answers
165 views

How can I create an equation for a Gaussian distribution based on a sum of a series?

I am trying to create an equation that will generate a Gaussian distribution such that y = the sum of f(x) in a series of integers 1->28. I have y and want to know what the value of x at each integer ...
7
votes
0answers
276 views

Does this calculation have a name, or a generic formulation?

Background I would appreciate help in identifying / explaining this operation: To calculate each of the $n$ values of $f(\Phi)$: sample from the distribution of each of $i$ parameters, $\phi_i$ ...
0
votes
1answer
311 views

Set x increases by 1, Set y increases by 3. Need help with a function that will take $x_n$ and give me $y_n$

Two sets x = 1,2,3,4,5... y = 1,4,7,10,13... I need to write a function $f(x_n) = y_n$ I found that if I take a number from x double it subtract 2 add the ...
3
votes
0answers
175 views

Definition of functions based on “fuzzy” truth table

I'm stuck on this problem: I have a "truth-table" (well, I don't know if it can be called truth table, if there aren't true/false values only): ...