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

learn more… | top users | synonyms

1
vote
1answer
58 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
-1
votes
1answer
33 views

Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
0
votes
1answer
22 views

Print Binary Tree Diameter Path [duplicate]

Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT. Print the Longest leaf to leaf path in a binary tree and its ...
1
vote
1answer
28 views

primitive recursion in the lambda calculus

I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: ...
0
votes
0answers
21 views

Poly-variadic Y combinator

I have written a lambda calculus interpreter, and it seems to work. I cant find the combinator for something I want though. I want to be able to define an arbitrary number of mutually recursive ...
6
votes
1answer
106 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: ...
2
votes
2answers
61 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 ...
2
votes
0answers
17 views

What would be the time complexity if a recursive function is inside a loop? [duplicate]

I am confused in calculating the time complexity for a recursive function inside a loop. ...
1
vote
2answers
88 views

How many recursive calls does it take to compute binomial probability weights?

I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen ...
6
votes
1answer
80 views

How can the class of tail recursive functions be compared to the classes of PR and R?

How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)? The computation of a PR function always halts. This ...
0
votes
0answers
15 views

Time complexity with flooring of nested function calls [duplicate]

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
2
votes
1answer
37 views

Upper bound of algorithm with flooring

Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm. $$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$ $$T(1) = 0$$ Solution is given as: $$T(n) = ...
5
votes
1answer
63 views

How to show all possible implied parenthesis?

Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ? (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = ...
0
votes
0answers
18 views

How to apply recursion in this problem [duplicate]

Problem Statement : You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one ...
1
vote
3answers
65 views

Value returned by recursive function

(pseudocode) ...
2
votes
1answer
44 views

Induction proof of alpha-beta search

Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works? My first thought is that the algorithm introduces an $[\alpha,\beta]$ ...
0
votes
0answers
9 views

recursion trees and big theta bounds [duplicate]

Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = ...
2
votes
3answers
58 views

Recursive function problem

This might seem very simple but it's been giving me lots of headaches. For example if I run f(12345) the result is 5310135. I understand why it would return 5310, the rest of 135 is what is giving ...
-1
votes
1answer
44 views

Recursive definition of the set of strings over an alphabet [closed]

The problem is the following: Write the recursive definition for the set of all Strings Q over the alphabet {a, b} (i.e. the set of strings consisting of a's and b', for example a, baba, ...
1
vote
0answers
18 views

Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?

I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says: Furthermore, the element stored in min does not appear in any of the recursive $vEB( ...
2
votes
5answers
294 views

Do recursive algorithms generally perform better than their for-loop counterpart?

I'm sure this is not a challenge for you but it remains an open question for me: Is it wise to prefer a recursive algorithm over its for-loop counterpart? E.g. take the evaluation of the natural ...
4
votes
1answer
121 views

Recursive definition of a language given the regular expression

Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$ I know that there is a DFA that accepts this language, and furthermore, that the regular ...
0
votes
1answer
100 views

Help needed with lesson on recursion

I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example". I understood the beginning and I even made a program that calculates $X$ to the power of $N$ ...
4
votes
0answers
82 views

Why can't a programming language be both fully recursive and polymorphic

In my theory of computation class last Spring my professor said in passing that a programming language cannot be both fully recursive and polymorphic. I didn't think much of it till now? What does it ...
1
vote
3answers
260 views

If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or ...
4
votes
1answer
46 views

Proof by induction over rules for mutually recursive relations

Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified): ...
-1
votes
1answer
39 views

Proving correctness of a recursive algorithm using induction

For the program mean(A,n) if n = 1 then return A[n] else return A[n]/n+mean(A,n-1)*(n-1)/n end Show that if the recursive call to ...
-2
votes
1answer
71 views

Using dynamic programming to find the number ofl increasing subsequences [closed]

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing ...
3
votes
1answer
125 views

Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met: In-place partitioning is used. This unstable partition requires O(1) space. After partitioning, the ...
0
votes
0answers
24 views

Recursive macros and termination of assembler

A debate has arisen in the course of using an assembler (which does a bit of preprocessing first, but is mainly a static assembler): This particular assembler allows recursive macros to be defined, ...
0
votes
0answers
19 views

Solving $T(n)=2T(n/2) + n \lg n$ , For ex: Counting inversions implemented with full mergesort [duplicate]

How to solve the recurrence equation $T(n)=2T(n/2) + n \lg n$ For ex: I implemented "Counting inversions" with a full mergesort instead of just using merge part, So the outer complexity will be $n ...
2
votes
1answer
49 views

Undecidable definition of pure function?

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
0answers
77 views

What is the complexity of this recursive merge of two ordered Python lists?

This is not an assignment, but it is related to my Data Structures class. I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + ...
2
votes
1answer
66 views

Time complexity of linear program? [closed]

I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of ...
1
vote
1answer
56 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$ ...
1
vote
1answer
101 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 ...
2
votes
3answers
152 views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
1
vote
0answers
228 views

Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an ...
0
votes
1answer
84 views

Algorithm to compute a recursive function on a given set [closed]

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
0
votes
1answer
72 views

Recursive algorithm to compute a sum of product like function

I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows $F_{i,j}(m)=\sum_{t=j}^{m}\left [ ...
0
votes
0answers
167 views

Finding the $k$th smallest element in union of two sorted arrays

I know that this problem is solvable in linear time with a merge but I want to get a sub-linear algorithm. What I came up is that, if a[k] < b[k] then the $k$th ...
-2
votes
1answer
147 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ ...
0
votes
1answer
25 views

Something wrong with this definition of factorial with structural recursion? [closed]

In The Algebra of Programming page 5, the authors defined structural recursion foldn (c, h) over natural numbers: ...
-2
votes
1answer
83 views

Finding the time complexity of fibonacci sequence [closed]

I tried it as follows and would like to know if it is correct.
0
votes
1answer
94 views

Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
0
votes
1answer
34 views

What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
0
votes
1answer
79 views

Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
1
vote
1answer
163 views

Find one-variable recursive formula for running time of Karatsuba multiplication

I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion ...
3
votes
2answers
75 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...