Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

0
votes
0answers
8 views

Using Iterative method to find recurrence relation vs Master Theorm

I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem. T(n) = 5T(n/2) +n^2 = 5^2 T(n/4) + (5/4)n^2 + n^2 = ...
0
votes
0answers
25 views

Compute a function given as recurrence in logarithmic time

$$g(n) = \begin{cases} n &&&& \text{$n$ = 1,2,3}\\[2ex] g(n-1) + 2 \cdot g(n-3) &&&& \text{$n \geq 4$}\end{cases}$$ Given this function, I ...
0
votes
0answers
27 views

Recursion func to get list of objects

I want to write code that returns a list of $X_i$ values base on this logic. Assuming $X> 1$ a positive non decimal number, and $n$ is the number of objects: $X_n = X-X_1$ $X_i = X_{i+1} / 2$ $...
0
votes
0answers
27 views

Big-O of a recursive function [duplicate]

just wondering, what's the big o of this function, let say the initial value of the parameters is as following: ...
0
votes
1answer
17 views

Is any State Space Tree always Binary Tree?

A backtracking algorithm generates, explicitly or implicitly, a state-space tree. Introduction to the design & analysis of algorithms / Anany Levitin I wonder that whether the saying ...
1
vote
1answer
75 views

Answering questions about the recurrence of certain aspects of an algorithm

I am thoroughly confused by a problem that was brought up in class: Given the following pseudocode for a function RANDOM which generates a random number based off of recursion: ...
0
votes
0answers
43 views

What is the time complexity of this power algorithm?

I'm trying to learn more about time complexity of algorithms on my own, but it comes very confusing when recursion gets into it. The power function calculates $x^...
0
votes
2answers
29 views

Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
0
votes
1answer
59 views

Induction of recursive function [on hold]

i'm trying to do these questions on an algorithms book, how might i use induction on these recursive functions like 1-7? Questions are in image
1
vote
3answers
74 views

Time complexity of function vs return value

I came across following problem: Find the time complexity of below recurrence relation: $T(n)=\begin{cases} & 2T(n/2)+C; & n>1\\ & C;&n=1 \\ \end{cases}$ The solution ...
-1
votes
1answer
57 views

Finding recurrence equation for a variant of insertion sort [closed]

I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort ...
1
vote
1answer
20 views

How to implement recursive solution with large number or parameterized possible next steps

I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom ...
2
votes
1answer
90 views

What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
1
vote
0answers
25 views

Is this solution is bad for the coin change problem? [closed]

was doing coin change problem as an assignment(didnt know before), after came with this solution i checked the solutions available couldnt find a similar one like this, just curious. removing the ...
1
vote
1answer
35 views

Asymptotic bound of a recursive function

Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N? ...
1
vote
2answers
67 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
0
votes
0answers
27 views

Understanding How to Flatten a Nested Function System

There are at least two ways to flatten out a nested function. Both of them need to keep a certain amount of state to accomplish this. The two ways are: By creating several boolean variables for each ...
14
votes
3answers
4k views

Will this program terminate for every Integer?

In a Part Test for GATE Preparation there was a question : f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) I answered "It will terminate for all ...
2
votes
1answer
271 views

Water Jug Problem

I was reading an article on Water Jug Problem. The problem is -You are given a m litre jug and a n litre jug where 0 < m < n. Both the jugs are initially empty. The jugs don’t have markings to ...
-2
votes
1answer
42 views

Solving double recurrence relation

How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(...
2
votes
0answers
22 views

Reference request: Leaf-heavy master theorem algorithms

I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication. Are there other recursive ...
0
votes
1answer
89 views

Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
0
votes
2answers
38 views

Recursive relations in binary trees

I have an exercise in my algorithm's Course for which I have the correction but do not understand it. 1.Exercise . Let Th be a full binary three of height h(meaning all the levels all completely ...
0
votes
0answers
203 views

Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
4
votes
0answers
45 views

The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
0
votes
0answers
26 views

Recursive formula for finding ways to spend x amount of money on y items [duplicate]

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
0
votes
2answers
147 views

Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
0
votes
0answers
38 views

Demonstrate that algorithm is O(n)

So i have this algorithm that checks if an binary tree is a binary search tree: ...
3
votes
2answers
53 views

Alan Perlis Epigram on Recursion

So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis: Recursion is the root of computation since it trades description for time. -- ...
0
votes
2answers
50 views

Proving the correctness of a square summing algorithm

int sumHelper(int n, int a) { if (n==0) return a; else return sumHelper(n-1, a + n*n); } int sumSqr(int n) { return sumHelper(n, 0); } I am supposed ...
0
votes
2answers
191 views

How does in-order traversal in Binary search tree works (recursion)

I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript. The code is typical BST implementation with methods to support ...
1
vote
1answer
133 views

Understanding Martin Farach's suffix tree algorithm

I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have [1] [2] seems to skip over whatever details that would make me comfortable ...
0
votes
0answers
61 views

Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
1
vote
1answer
32 views

Number of calls with length 2 array in quick-sort

I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion: $$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \...
1
vote
1answer
25 views

Recurrence equation calculation

I have a recurrece equation Changed notations: $\qquad\displaystyle G(W) = \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$, I am not sure if I understand $\ w_i $ correctly. On each ...
0
votes
1answer
125 views

Finding the longest overlapping interval pair

Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, b\}$. An overlap is defined as $|S_1 \cap S_2|$. Example: $[3,6]$ and $[5,9]$ overlap on $[5,6]$ ...
3
votes
1answer
44 views

Generating all words of length $n$ avoiding $A^2$ and $B^3$

I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing? I ...
1
vote
1answer
38 views

How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$? [duplicate]

How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$? I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working.....
1
vote
0answers
17 views

Knight's Tour Parberry algorithm: 4 knight's tour merge procedure

I'm implementing Parberry's algorithm for closed Knight's tour problem. Brief idea of the algorithm: split the board in $4$ parts, find the tour on them recursively then delete $1$ edge in each part ...
0
votes
0answers
94 views

Doubt on analysis on time and space complexity of creating n² tuples

This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used ...
8
votes
2answers
333 views

How to derive dependently typed eliminators?

In dependently-typed programming, there are two main ways of decomposing data and performing recursion: Dependent pattern matching: function definitions are given as multiple clauses. Unification ...
2
votes
2answers
255 views

Solve every problem with recursion [duplicate]

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks
1
vote
2answers
609 views

Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the ...
0
votes
0answers
41 views

Is there a proof for the halting problem that does not involve an infinite nest of functions? [duplicate]

I have been doing a fair amount of research about the halting problem. Most solutions I come across have the following pattern: We assume we have a program H that solves the halting problem. We then ...
2
votes
0answers
54 views

number lesser than a given number composed of only binary numbers

Give a decimal number, such as 123. Need to figure out all smaller numbers lesser than 123 made up by ...
0
votes
1answer
262 views

Recursive Algorithm Copying Array vs. Time Complexity

If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$. However, what will occur if the array is NOT passed by referenced and rather by value. ...
0
votes
0answers
46 views

Time Complexity — Recursion

It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm. Here is the algorithm in a pseudo-pseudocode (yes, two ...
1
vote
0answers
77 views

Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
1
vote
0answers
54 views

A question on analysis of the time complexity of a recursive branching algorithm

I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows: Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
0
votes
0answers
48 views

How to “convert” a top-down solution to a bottom-up algorithm? [duplicate]

When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion. Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...