New answers tagged

0

You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$. $$f(n, i) = \begin{cases} 1 & \text{if } n =0\\ f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\ 0 & \text{otherwise}\\ \end{cases}$$ Then $...


2

In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement. Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I ...


0

If you apply the recursive formula again to $T(n/2)$ you get the following: $$ T(n) = \sqrt{2}\cdot T(n/2) + \sqrt{n} \\T(n)= \sqrt{2}(\sqrt{2}\cdot T(n/4) + \sqrt{n/2}) + \sqrt{n} \\T(n)= 2\cdot T(n/4) + 2\sqrt{n}$$ For this formula you are now probably able to draw a recursion tree.


1

I do not have a strong mathematical background, but I am afraid that recursive functions cannot always been written in closed form. ex1. f(n) = sum([1,2,..,n]) can be written as f(1) = 1 f(n) = n + f(n-1) Of course f(n) = n*(n+1)/2 ex2. f(n) = prod([1,2,3,4,..n]) = n! f(1) = 1 f(n) = n * f(n-1) No known closed formula :( (I don't even know how to prove ...


2

Nicest version of the Akra-Bazzi theorem I've seen is the one in Lehman, Leighton, Meyer "Mathematics for Computer Science", the discussion starts at page 1019. An (older) print version is available. No proof, though. Would need to slough through Leighton's note to verify that the lecture notes/book version is right (it has somewhat different conditions, ...


0

You can use the variant by Leighton "Notes on Better Master Theorems for Divide-and-Conquer Recurrences". Lehman, Leighton and Meyer in "Mathematics for Computer Science" on page 1019 state a simplified version: If you have $T(n) = \sum_{1 \le i \le k} a_i T(b_i n + h_i(n)) + g(n)$, where $a_i > 0$, $0 < b_i < 1$, $g(n) > 0$ such that $\lvert g'(...


3

You are unsure how to answer the question. When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come. A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls. Now ...


1

Without going into the details, you are looking for something that's known as a Gray code. Any cyclic Gray code that has the all zero bitstring at the opposite part of the cycle as the all one bitstring gives a minimal expected solution time assuming an uniform random input.


2

Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$. Input: coin 0, coin 1, coin 2, ..., coin $n-1$ Procedure: $\quad$ If all coins face the same side, return. $\quad$ For $i$ from 1 to $2^{n-1}-1$ inclusive: $\quad\quad$ If $i$ is divisible by $2^k$ but not $2^{k+1}$: $\quad\quad\quad$ Flip coin $k$ $\quad\quad\quad$ If ...


1

We can use master's method to solve this. a = 2 b = 3 n^(log(a)base(b)) = n^(log(2)base(3)) = n^(0.63) Now, f(n) = 5n f(n) > n^(0.63) so, if time complexity = T(n), then using master's theorem: T(n) = Theta(5n) = Theta(n) Without the use of master's theorem: using substitution method T(n) = 2 * T(n/3) + 5n = 2 * [2 * T(n/(3^2)) + 5(n/3)] + 5n ...


3

Your understanding of how recursive code maps to a recurrence is flawed, and hence the recurrence you've written is "the cost of T(n) is n lots of T(n-1)", which clearly isn't the case in the recursion. There's a single recursive call, and a multiplication of the result. Assuming the numbers aren't large, the multiplication is constant time, and it's a ...


Top 50 recent answers are included