Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

learn more… | top users | synonyms

1
vote
1answer
21 views

If $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $. How is the upper bound achieved?

Trying to show that if $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $ using a tree, I do know that taking the shortest path gives a lower bound of the number of steps equivalent to ...
-2
votes
0answers
52 views

What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
0
votes
2answers
22 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
0
votes
1answer
16 views

Is it possible to solve a recurrence with max()?

I have the following problem. Imagine there is a set $P=\{p_1,p_2,p_3\} \subset \mathbb Z $ and I want to describe how it changes in time. Informally, the rule is simple: At every time-step, subtract ...
0
votes
0answers
23 views

Runtime of Algorithms (Recurrence&Induction)

Two algorithms are given: $$T_A(n) = (\log_4(n) + 1) \cdot n\quad\text{and}\quad T_B(n) = 4 T_B\left(\frac{n}{4}\right) + n^\alpha$$ $$T_B(1) = 1; \alpha \in \mathbb R_+; n = ...
0
votes
0answers
18 views

Compute smoothed probabilities for EM algorithm

In order to compute the expected value of log-likelihood in EM algorithm, we use 3 different probabilities Forecast (predictive) probabilities Inference probabilities Smoothed probabilities ...
-1
votes
0answers
21 views

How does this prime factorization algorithm work?

(Not sure if this is the best place to ask, please tell me if that is the case, I wanted to ask on SO but I don't understand the math) This is the code: ...
0
votes
0answers
25 views

How does this self referencing (circular reference) equation terminate (i.e. not create a paradox?)

I'm working with a financial equation which seems like it should result in a paradox but I'm told doesn't, however I haven't been told why it doesn't. (I don't work in the field I'm a programmer ...
0
votes
1answer
35 views

Algorithm for the independent domination number

A dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in ...
0
votes
3answers
36 views

Write a recursive algorithm for locating the max number amongst k integers.

Iteratively, I know how to find the max number: Set Max = List[0], for k in range(len(List)), if List[k] > Max, Max = List[k]. Return Max. Recursively, I'm not quite sure. Here is my idea: I ...
1
vote
1answer
21 views

Algorithm for generating all elements of a set consisting of specific $n$-tuples

I was working on functional analysis last night, and then my mind got distracted by the following problem. Consider a set $$I=\{0,1\}$$Now consider a subset of $\mathbb{R^n}$ $$X=\{(x_1,x_2,\dots ...
0
votes
1answer
39 views

Recursive Definitions

I have two recursive definitions that I need to determine if they are correct. The first one is: The set S of all positive integer multipliers of 5 can be described by the following recursive ...
0
votes
0answers
33 views

Iterative methods to find roots

I'm trying to do optional exercises for my numerical methods class. I'm stuck in this one right now: Consider the function $f(x)=-e^{-2x}+3x$. a) Prove that $f$ has an unique real root. ...
0
votes
1answer
17 views

Branching/layered optimisation - how?

Imagine you had a collection of systems each with their own constraints and objective functions to optimise (likely similar in form to each other), these then collectively aggregated into a ...
0
votes
2answers
25 views

Recursive type for $ y_{k}=2^k\tan(\frac{\pi}{2^k})$

Given the sequence $ y_{k}=2^k\tan(\frac{\pi}{2^k})$ for k=2,3,.. prove that $ y_{k} $ is recursively produced by the algorithm: $$ y_{k+1}=2^{2k+1}\frac{\sqrt{1+(2^{-k}y_{k})^2}-1}{y_{k}} $$ for ...
1
vote
1answer
20 views

Find a function f(n) such that T(n) is $\Theta(n \cdot log(n)) $

Find a function f(n) such that $ T(n)=16 \cdot T(\frac{n}{4}) + f(n) = \Theta(n \cdot log(n)) $ Also, another section of the question is where $T(n) = \Theta(n^{2})$ I've tried using the master ...
1
vote
1answer
29 views
0
votes
0answers
16 views

Contour and perimeter recognition in binary image

I need to detect contour (object) and find the perimeter of a detected object. For example, I have the following image: http://i.stack.imgur.com/40TTX.png All images are binary, so they consist of ...
0
votes
2answers
43 views

Prove a Recursive Formula by Induction?

So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given. I ...
0
votes
1answer
21 views

Implementing Recursive descent algorithm for PWL Approximation

I am currently trying to linearise a convex function at hand (an M/M/1 curve) using piecewise linear functions. Since I wanted the approximation error to be as low as possible, I searched for some ...
0
votes
1answer
50 views

Recursive approach for computing $(a,b) \mapsto a^b$

As a programming exercise I was asked to implement a recursive approach for computing $a^b$ given two real $a,b \in \mathbb R, a>0$. I assume this task has a typo, as a recursive approach makes ...
1
vote
2answers
28 views

How can I solve this linear recursion?

Let be $a_{0}=1,a_{1}=1,a_{n}=4a_{n-1}-2a_{n-2}$ if($n\ge 2)$ Should I first find the generating function of the recursion and after that? I solved it with Wolfram Alpha and after it the result is ...
0
votes
0answers
13 views

Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
3
votes
0answers
50 views

Count number of m-subsets with xor = 0 [closed]

Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let ...
0
votes
2answers
65 views

Define algorithm using divide and conquer paradigm [closed]

Q:Describe a Θ(n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference. (From what i understand, we first apply merge sort to our ...
2
votes
2answers
82 views

A square root solving algorithm invented by my friend

Recently, my friend told me a square root algorithm: $$ \left\{ \begin{array}{lll} p_{n+1}&=&p_n+aq_n \\ q_{n+1}&=&p_n+q_n\end{array}\right.$$ Finally, $p_n/q_n$ is near $\sqrt{a}$. ...
0
votes
0answers
15 views

recurrence algorithm unfolding with answer, need explanation

SO the question is to prove $O(n\log n)$ hence figure out $f(n)$ correct? why does $n = 2^{2^k}$ what is so special about $2^{2^k}$ can i use another number? this answer is using substitution? I ...
1
vote
2answers
51 views

recurrence algorithms, algebra issues?

So we're given a problem to solve... no other instructions.. the answer is given as well. I am having trouble understanding how this problem is unrolled. I understand that $\sqrt{2^{2^k}}$ can ...
2
votes
1answer
29 views

Proving $T(n) = T(n-2) + \log_2 n$ to be $\Omega(n\log_2 n)$

As title, for this recursive function $T(n) = T(n-2) + \log_2 n$, I worked out how to prove that it belongs to $O(n\log n)$; however I'm having trouble proving it to be also $\Omega(n\log n)$, i.e. ...
0
votes
0answers
12 views

Finding the Reccurrence of a Periodic Sorting Network

Consider this Periodic Network of input size $n = 8$. I am trying to find an asymptotic approximation of the size (# of comparators) for such network. My attempt: Since there are $n$ inputs, there ...
0
votes
2answers
30 views

Not understanding the steps in Simplifying a Series

I am hoping someone can explain why the second step has a $$o(\lg^k{n})$$ and then in the next step how the Riemann sum is simplified and the change of sign. $$ B = ...
0
votes
1answer
33 views

Recurrence relation with ternary strings

Express, as a recurrence relation, the number of ternary strings of length n that contain either 2 consecutive 0's or 2 consecutive 2's. Don't forget to include the base case. Can someone help me ...
4
votes
1answer
47 views

Recursive Sum of Previous Term and its Inverse

Can anyone help me with finding a closed form for $F_n$ where $$F_0=x_0$$ $$F_{n+1}=F_n+\frac{1}{F_n}=\frac{F_n^2+1}{F_n}$$ I could imagine this already having been done, in which case I'd appreciate ...
0
votes
0answers
40 views

How to solve recurrence $T(n) = T(n/3) + T(2n/3) +n$ using Master Theorem

I'm trying to solve the following recurrence using Master Theorem, but I'm not used to seeing recurrences with to terms ( i.e. T(n)) for the cost of operations. I'm pretty sure that a should be 1 and ...
2
votes
3answers
65 views

Compare five ways of solving cubic equation by iterations (nested expressions)

Say we have a depressed cubic equation in the general form: $$x^3-bx-c=0$$ There are basically five ways of solving it by iterations. Let's consider them in no particular order (the names are my ...
1
vote
0answers
29 views

Is there a decimal based way to take roots or exponents?

We all know about division using decimals and places, you just keep dividing each digit place and move on to the next one. I was wondering if there was a similar method by which you could manually ...
0
votes
0answers
44 views

Average time complexity on finding all common substring of a string

Background Information & Research I'm working on an algorithm where you have to find all common substrings for a given string. For instance find("ABC", "ABCD") would result in {A, AB, ABC, B, BC, ...
1
vote
1answer
64 views

Ackermann's Function

$A(m,n) = n+1$ if $m=0$$A(m,n) = A(m-1,1)$ if $n=0$$A(m,n)= A(m-1,A(m,n-1))$ This function blows off( I mean increases drastically) after a certain point. For example,$ A(2,4) = A(1,A(2,3)) = ...
0
votes
0answers
22 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : ...
0
votes
1answer
29 views

Solve the recurrence using the Master Theorem: $T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n$

I am trying to solve the recurrence: $$ T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n. $$ I tried to apply the Master Theorem but it didn't get me anywhere: $$ a=5,\; b=4\; \text{ and } f(n) = n\lg ...
1
vote
0answers
28 views

Infinite series, continued fractions, nested radicals and such - is there a general recursive algorithm theory?

The nature of infinity and irrational numbers (among other things) always gave me trouble. But recently I learned to think about infinite sequences in terms of recursive algorithms and their time ...
0
votes
0answers
19 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
2
votes
1answer
52 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
0
votes
0answers
50 views

Specify an O(logn) algorithm which either finds an i, where i is an element of {1,2,…n} such that S[

Let S be an array of n integers such that S[1] < S[2] <...< S[n] Specify an O(logn) algorithm which either finds an i, where i is an element of {1,2,...n} such that S[ i ] = i or else ...
1
vote
1answer
64 views

Is the definition of recursive function unchanged if we restrict substitution to binary composition?

When defining recursive functions, are the following two statements equivalent?$$f:\mathbb{N}^n\rightarrow\mathbb{N}^m, g:\mathbb{N}^m\rightarrow\mathbb{N}^k \text{ recursive}\implies g\circ f \text{ ...
2
votes
0answers
115 views

Finding a solution to $\sum _{n=1}^{n=k} \frac{1}{n^x}+\sum _{n=1}^{n=k} \frac{1}{n^y}=0$

Scroll down to the update to see what I am meaning. The Mathematica program below finds a solution to the equation: $$\sum _{n=1}^5 \frac{1}{n^x}+\sum _{n=1}^5 \frac{1}{n^y}=0$$ My question is if you ...
0
votes
0answers
117 views

Counterexample for Algorithm of Isomorphism testing of Non-Symmetric Matrices

Claim: $E, F$ are non-symmetric 0-1 matrices of dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check ...
1
vote
1answer
28 views

Algorithm for equality of trees of restricted depth

Are there any efficient algorithms to decide whether two trees of limited depth, where all nodes have a finite number of childs, are equal interpreted as finite sets with the leaves the "atomic" ...
3
votes
2answers
169 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
1
vote
0answers
57 views

Number of Hamilton paths in an extremely dense undirected simple graph

What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)? I was thinking of the following ...