# Tagged Questions

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

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 ...
58 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, ...
69 views

29 views

125 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 ...
129 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 ...
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" ...
170 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?
59 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 ...
95 views

### Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 ...
37 views

### I want an upper bound for a real function f(x,y,z) - prime counting

The function $f:\mathbb R^3\to\mathbb R$ is: $$\displaystyle f(x,y,z)=\frac{x}{yz}-\frac{\lfloor x/y\rfloor}{z} , \; \text{where}\,\; x,y,z>1.$$ If there is an upper bound less than 1, then it is ...
29 views

### When the integers got upset.

I have been stuck with this problem for quite large time. https://www.hackerearth.com/code-monk-bit-manipulation/algorithm/when-the-integers-got-upset/. In short what is says is: There are two arrays ...
35 views

### Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
80 views

23 views

### Factorial Series Written As Recursive Definition

I have a factorial series as shown below: $$(2n+1)!~\text{for all n \geq 0}$$ And I would like to know if the recursive definition that I wrote is accurate: \begin{...
25 views

### Recursive Definition of a Series

I have a series such as the one below: $$2^n(\sum\limits_{i=2}^{n+1}i)\text{ for all n \geq 1}$$ I need to write a recursive definition for it. Here's what I have so ...
28 views

### Summation of differences in exponent

Came to this summation during an algorithm analysis problem and any help would be much appreciated:$$\sum_{j=1}^n3^{n-j}$$
31 views

### How to give a recursive definition and a direct formula and prove that they both are equivalent.

How to give a recursive definition and a direct formula and prove that they both are equivalent. for example, 10,13,16,19,22,25 I know the formula for this is a,a+d,a+2d,a+3d,... 7,49,343,2401,...
44 views

### given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two?

this is the question given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well. My ...
28 views

### Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
19 views

### Nodes equation: can't find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level $N$ where $X$ is located to narrow our ...
30 views

### Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
39 views

### A recursive definition

I have this problem: Q4 of this Prove by induction that no matter how the dots are coloured red and blue, it is possible to have a successful trip around the circle if you start at the correct ...
### Asymptotic bounds for $T(n)=T(n-2)+n$
I am trying to figure out how to find the Asymptotic bounds for $T(n)=T(n-2)+n$ and I am pretty sure that I need to use the substitution method. I have what I believe is a proof using the Subtract ...