# Tagged Questions

a definition of a sequence where later elements are expressed as a function of earlier elements.

38 views

28 views

### $N$-th term of a quadratic recurrence [closed]

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ ...
28 views

### Runtime analysis with recursion factor

I have this code: if n is even { for i=1....n for j=1...i print j return 8*foo(n/2) } Asking to calculate the running time $T (n)$. I thought at first ...
76 views

### Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
114 views

### Solving T(n) = 2T(n/2) + log n with the recurrence tree method

I was solving recurrence relations. The first recurrence relation was $T(n)=2T(n/2)+n$ The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree ...
30 views

### Solving recurrence relation when cost of all combining steps is constrained

I have a recurrence relation $T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n)$, where each $0 < d_i < 1$, $f(x) > 0$ for all $\, x > 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$. ...
71 views

101 views

### Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the “+1” part?

I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain ...
50 views

### Find Big O using Iteration

I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step. $T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ ...
195 views

### Using the Master theorem on a recurrence with non-constant a

I am trying to solve the following equation using master's theorem. $T(n) = 3^n T(\frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what ...
72 views

### Solving the recurrence $T(n)=T(n-1)*T(n-2)$

I have been trying to solve the following recurrence: $$T(n)=T(n-1)*T(n-2)$$ The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$. I started by taking the $\log_{2}$ of both sides to ...
31 views

### Efficient algorithm for swapping dimensions for an N-dimensional matrix

I have data stored in N-dimensional matrixes (i.e. Arrays nested N layers deep). Is there a good standard solution - other than brute force - to the following two problems I want to swap 2 ...
44 views

### Number of levels in the recursion tree

While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log_{b}n$ when $b$ is a constant....
135 views

### What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037. This is my proposed solution to compute the $n$th value: ...
96 views

### Recurrence relations when function call is made inside loop

int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n – k); return x; } What is the value of fun(5)? I ...
I'm given the following recurrence equation: \begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when n > 1 is even}\\ T(n) &= T((n+1)/2) + 1 && \... 1answer 45 views ### Recurrence for the number of strings defined by a homomorphism Let h be the homomorphism defined by h(a) = \mathtt{01}, \quad h(b) = \mathtt{10}, \quad h(c) = \mathtt{0}, \quad h(d) = \mathtt{1} $$and extended to strings in the usual way. Then the inverse ... 0answers 13 views ### Q: Resources where i can practice creating recurrence relations from code? [duplicate] I'm having difficulty creating recurrence relation from (pseudo)code. Are there any recommendations or resources I can use to get better? 1answer 399 views ### Big-O proof for a recurrence relation? This question is fairly specific in the manner of steps taken to solve the problem. Given T(n)=2T(2n/3)+O(n) prove that T(n)=O(n^2). So the steps were as follows. We want to prove that T(n) \... 1answer 66 views ### How to resolve a recurrence relation in the form of T(n) = T(f(n))*T(g(n)) + h(n) I am basically trying to solve the following question: Given a set P = \{\{1\},\{2\},\dots,\{n\}\} of n sets of elements, our aim is to merge these elements into one set. At each step, sets can ... 0answers 30 views ### Understanding exponential computation by digit recurrence I've met in a book the following algorithm that computes the exponential: Input: t, n (n is the number of steps) Output: E_n \begin{array}{l} \mbox{define t_0 = 0 ; E_0 = 1} \\ \mbox{... 1answer 80 views ### How to solve T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)? [duplicate] How do I solve the recurrence relation T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k), for constant k? I am told that the answer does not depend on k. 1answer 82 views ### Solving recurrences by substitution method: why can I introduce new constants? I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is: Show that solution of T(n) = T(\lceil n/2\rceil) + 1 is O(\lg n) So, by big-O definition I ... 1answer 31 views ### Time complexity of a Divide and Conquer I have Master theorem for finding complexities but the problem is Master theorem says For a recurrence of form T(n) = aT(n/b) + f(n) where a \geq 1 and b > 1, there are following three cases:... 1answer 55 views ### Master method recurrence question [duplicate] This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified f(n) (as denoted below). For a recurrence of$$T(n) = a T(\frac{n}{b}) +...
I am having problem with solving the following recurrence relation. $A$ is a set, there are at most $k+1$ of this set and $|A|$ is at most $n/2$. $T(n) = O(n log k) + \sum_A T(|A|)$ I guess it can't ...