Tagged Questions

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

learn more… | top users | synonyms

4
votes
1answer
26 views
0
votes
1answer
30 views

How to find if an array has at least 10 unique integers in $O(\log n)$?

I am given a sorted array of integers. I want to find out if the array has at least 10 unique integers. I know this can easily be done with an algorithm that runs in $O(n)$ simply by going through ...
1
vote
0answers
30 views

Finding the explicit form of the recursive function $P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor$

I'm trying to find the explicit form of the recursive function $$P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor\;.$$ First, let me explain what this ...
2
votes
5answers
95 views

How to give a good guess to the recurrence relation problem

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
0
votes
0answers
12 views

Calculate a recursive function

Says I have this function : $f(n) = \begin{cases}0 & n =0\\ f(n-1) + n & \ n >= 1 \end{cases}$ Easy to see, It's a recursive function which will keep return $f(n) = f(n) - 1 + n$ until ...
1
vote
2answers
33 views

Optimal Number of White Balls

There are C containers, B black balls and infinite number of white balls. Each container should have at least one ball. Each of the containers may contain any number of black and white balls. Action ...
1
vote
0answers
25 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ ...
-1
votes
0answers
61 views

MERGE(L1,L2) two sorted list [closed]

Merge(L1, L2), below, is a function which merges two sorted linked lists L1 and L2, and outputs a single sorted linked list. By "sorted", we mean increasing order. ...
1
vote
1answer
44 views

Generate all permutations of a string containing repeated characters

I was writing a program to print all the permutations of a string. I came up with the following: ...
0
votes
0answers
16 views

Binary Search when no “fixed” answer…? (Font Sizing)

So I'm trying to figure out how best to implement a binary search algorithm to find the "optimal" font size for a piece of text to fit into a given space, to the nearest 0.5pt. My understanding is ...
0
votes
1answer
17 views

Recurence Problem. - Solve either by substitution or Expansion

Function T(n) is defined by the following recurrence relation: $$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$ $$ T(0)=1 $$ How would I Solve by substitution and/or Expansion? Note: ...
1
vote
1answer
35 views

Using Extended Euclidean Algorithm

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
5
votes
2answers
43 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
0
votes
0answers
18 views

find the explicit form of recursive equation: $p_{n+1} = 3.4(1-p_n)p_n $

I'm trying to find the explicit form of recursive equation: $p_{n+1} = 3.4(1-p_n)p_n $ I can do this pretty easily using matrix iteration for linear equations, but I'm completely lost how to do ...
1
vote
1answer
29 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
2
votes
1answer
37 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
0
votes
0answers
11 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
1answer
28 views

Karatsuba multiplication algorithm of two 6 digit decimal numbers.

What are the min and max number of single digit multiplications, involved in recursive karatsubha multiplication of two 6 digit decimal numbers? I found different results on different numbers. But I ...
0
votes
1answer
72 views

Improving the Edit Distance Algorithm

I applied an Edit Distance Algorithm for similarity between two strings over the lowercase latin alphabet, where the first string has length $m$ and the second length $n$. However I want to improve ...
0
votes
1answer
48 views

Any way to get a Recursive function from its closed form?

For an exercise, the goal is to find a recursive definition for a certain function. the function itself is as follows: f(a,b) is the # of binary strings of length a and with b more 1s than 0s. eg: ...
0
votes
0answers
24 views

Sharing between 3 people

I have a problem on what im thinking since 2 weeks but i got no idea how to solve it. There are gifts with given values and we need to share these gifts between people fairly. Fair sharing in this ...
0
votes
0answers
13 views

Integer multiplication in 5T(n/3) [duplicate]

x and y has n bits x=x0*(10^2n/3)+x1*10^n/3+x2 y=y0*(10^2n/3)+y1*10^n/3+y2 x*y=x2y2+(x2y1+x1y2)10^n/3+(x2y0+x1y1+x0y2)10^2n/3+(x1y0+x0y1)10^n+x0y0*10^4n/3 now 9 multiplication of n/3 bit numbers ...
0
votes
1answer
21 views

A recurrence equation for the number of multiplications in an algorithm for computing powers

We were asked the to find the recurrence equation for the number of multiplications for the following algorithm as a function of N. For simiplicity, let $ N = 2^k $ and is a positive integer: I ...
0
votes
0answers
19 views

multiplication of two numbers in 6 of n/3 bits 6T(n/3)

multiplication of two numbers x*y ----> x =(x0*10^(n/3)+x1*10^(n/3)+x2) and y=(y0*10^(n/3)+y1*10^(n/3)+y2) x*y= x0*y0+x1*y1+x2*y2+x0*y1+x0*y2+x1*y0+x1*y3+x2*y0+x2*y1 it is 9 multiplication of ...
4
votes
1answer
35 views

Find a Recurrence Relation

I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21. i see the result is: ...
0
votes
1answer
21 views

Geometric sum of recurrence relation

I am reading the textbook Algorithm Design by Kleignberg and Tardos and I am having trouble on page 216. $$T(n) \le \sum_{j=0}^{log_2n - 1} \left ( \frac{q}{2}\right )^j cn = cn \sum_{j=0}^{log_2n - ...
5
votes
2answers
63 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
1
vote
0answers
29 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
0
votes
1answer
32 views

recursive equation: divide and conquer, subtract and conquer problem in one

I have a recursive equation that does not apply to the master method, since there is subtraction in the equation. I'd like to use the substitution method, but I have no idea where to start. Could ...
0
votes
0answers
10 views

recursive equations when the master method does not apply

I really struggle in solving recursive equations when the master method does not apply. For example, T(n) = 2T(n/2) + n/logn. I know the answer is supposed to be 0(nloglogn) so I tried using the ...
0
votes
1answer
19 views

Proving the correctness of a program

So I have this program below SquareRootRecursion that I need to prove is correct. However i'm not sure what it's pre and post conditions would be and how I would use those to prove it's correctness. ...
3
votes
2answers
45 views

Proof of recursivity of Shannon's Entropy

Does anybody know a book where the proof of recursivity property of Shannon's Entropy can be found? I mean this: $$H(q_1,...,q_n)=H(q_1 + q_2, q_3,...,q_n) + (q_1 +q_2)H( \frac{q_1}{q_1+q_2} , ...
0
votes
1answer
41 views

How to solve a recurrence

Apologies for this is a really trivial question, but I cannot figure out what to do after understanding the pattern of the function. Say I have this: $\begin{align} T(n) & = T(n-1) + 1/n \\ ...
1
vote
1answer
159 views

What are algorithm? Can we relate algorithm using set theory concepts?

What really algorithm are? Can we define algorithm as functions or in terms of set theory Can we reconvert proof using algorithm in set theory concept.For example, Theorem: A function defined on ...
1
vote
2answers
42 views

Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$

I have the following equation: $$T(n) = T\left({n \over 2}\right) + d n \log_2 n$$ A little investigation: $T(2^1) = 1 + 2d$ $T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$ $T(2^3) = T(2^2) + ...
3
votes
0answers
39 views

What's the next “recursion” here?

Plotting a single 3d helix is x = cos(t); y = sin(t); z = t; From this equation: x = [R + a cos(\omega t)] cos t y = [R + a cos(\omega t)] sin t z = h t + a sin(omega t) Comes the awesome ...
0
votes
2answers
48 views

Algorithm to calculate rating based on multiple reviews (using both review score and quantity)

First of all I must state that I am not a mathematician, so please correct me if I use wrong terminology. I am building a web application which needs to calculate the rating for each entity based on ...
1
vote
1answer
17 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
0
votes
0answers
23 views

Upper and Lower Bound Function for Recurrence Function

Suppose the first number in a sequence is 2, the second number is 3, and every following number is two times the (i-1)th number plus three times the (i-2)th number plus 2. (e.g. the first five numbers ...
1
vote
1answer
24 views

How can I solve the particular solution of the following recurrence (recursive) relation?

Having $a_n = 3a_{n-1} + 2a_{n-2} + 3·2^{2n-1}$ $a_1 = 12$ $a_0 = 0$ I solved the homogeneous part and got: $a^{{h}}_n = 1/12·2^n - 1/12·1^n$ This is the particular solution that I need to ...
1
vote
0answers
34 views

Using a Recursion Tree to solve the recurrence $T(n) = \sqrt n T(\frac{n}{2}) + 10n$?

I am attempting to solve the above recurence by giving tight $\Theta$ bounds. Assume that the logs here are all base 2! To solve a recursion tree as far as I understand, I need two things. The ...
1
vote
0answers
43 views

Algorithms recurrence equation using unwinding / substitution

This is homework for introduction to Algorithms this is what I have below. (25 pts) Use the direct unwinding to prove that the recurrence equation T(n)= 2T(n/2)+ nlogn has a lower bound of ...
0
votes
1answer
32 views

Recurrence Relation

So I am just making sure I am on the right track with this. I have the recurrence: T(n) = 2T(n-2) + 1 I am trying to solve this recurrence to get the time complexity T(n) = 2(2T(n-4) + 1) + 1 T(n) ...
5
votes
1answer
27 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
1
vote
0answers
29 views

Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?

The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=c$. Therefore, $z_1=c^2+c$, $z_2=c^4+2c^3+c^2+c$, etc. I have a function $f(n,x)$ ...
0
votes
1answer
34 views

recursive sequence - Which approach can I take to solve this equation?

Having this recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 4·3^n$ $a_1 = 36$ $a_0 = 0$ How can I solve this? I tried by characteristics roots and got stuck: *making $a_n=r^n$ $r^n = 5r^{n-1} - ...
1
vote
2answers
28 views

Can this recursive summation function be simplified?

I have the recursive function $$ a_n = \sum_{x=1}^n a_{n-x} a_{x-1} $$ where $a_0=1$ and $n$ is a positive integer. Looking at a graph of this function, it's very exponential in form, but it's not ...
-1
votes
1answer
43 views

Tight asymptotic upper and lower bounds

I have a equation: $T(n) = 4T(n/3) + n\ln n$ In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta ...
1
vote
1answer
27 views

Big O complexity of the partition function derived from this code?

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree. So far, I've figured out that ...
2
votes
1answer
25 views

How to solve the recursive complexity?

I have such recursive complexity $T(n) = T(n-2) + log(n)$. The problem is that I cant use a recursion tree or the master theorem. The only way, which I know, is to guess and then proof the answer. ...