Tagged Questions

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

32 views

Problem involving joining up three sided shapes

You are given a collection of three sided shapes. They each have certain type of texture. 0 being rough and 1 being smooth. ...
54 views

Asymptotic equalities in master theorem proof

In all proofs of master theorem I've found so far (Cormen et al., also here http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec19-master/mm-proof.pdf), there is essentially a following series ...
109 views

Minimally Good Sequences

Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$ Now ...
72 views

Generating Explicit function from Recursive Equations with Quadratic

Given the recursive function: $$U(0)=2\\ U(n)={U(n-1)}^{2}+1$$ How do I generate a explicit function? Please and Thank you!
71 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
130 views

81 views

How can I solve this recurrence problem?

Given a function $$f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0$$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
42 views

Show that running time of Quick Sort is $\mathcal O(n^2)$ when array contains distinct elements and is sorted in descending order

I'm trying to study running time for various algorithms. Now I have QuickSort. How exactly is the running time of an algorithm calculated, I know how quick sort works and the Asymptontic notations. I ...
39 views

Understanding recursive function for finding GCF of 2 numbers

So I get how this code works, but I don't understanding why it works. The function assumes input num1 > num2. Algorithms are hard for me to grasp, so please explain to me like I'm five. Heres the ...
19 views

Bounded Knapsackproblem Formula DP

I knew how the binary Knapsack works with Dynamic Programming. But, now I am interested. How does the recursive formula look like if I allow n€{0,1,2} of the same item to be in the Knapsack? The only ...
45 views

35 views

Recursive solution to “Number of subsets of a set without 3 following numbers”

so I got the following problem: For a given natural n number, let A be the set A={1,2,...,n} I need to provide a recursive solution that will return the number of possible subsets that doesn't ...
26 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
30 views

Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
41 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
72 views

This is recurrence $T(n)$ $T(n) = \begin{cases} c, & \text{if$n$is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if$n$is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ... 2answers 29 views Does this recurrence relation run in$ \Theta(n) \$?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
270 views

How to find a enclosed envelope with maximum points among a cloud of spheres? [ Concave Hull ]

I have a questions regarding the selection of the outer points (i.e. sphere center), among a collection of many spheres in 2D/3D space. The outer points is that when all of these points are ...