# Tagged Questions

29 views

### Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
44 views

72 views

### Recursively deleting every second element in a list

This question got me thinking. If you have a list of length n and recursively delete every other element from the list until only one element remains, is there any ...
160 views

### Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
76 views

### Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
94 views

### Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
94 views

### Generalization of the Tower of Hanoi?

What is the least possible number of steps for the Tower of Hanoi with $n$ discs and an arbitrary number $k$ of towers? For example, Tower of Hanoi with $4$ towers, $5$ towers, etc.
37 views

### How many number of ways are there for getting a special prime?

Definition of special prime : Any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) is a special prime. Thus -21, -30, 0, 5, 14 etc are special ...
66 views

### How do I go about manipulating this summation equation to solve it?

In my textbook, Introduction to Algorithms, the following is shown: And I believe I understand that. However, I have a similar equation to the one on the first line, but instead of ...
69 views

### How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
54 views

### How does my textbook come up with this statement? I don't believe it to be true.

My textbook (Introduction to Algorithms) states the following: When polynomially comparing $n^\epsilon$ and $lgn$, it states that $n^\epsilon$ is polynomially greater for any positive $\epsilon$. ...
79 views

### Where is the value of the variable $\epsilon$ obtained in the following explanation my professor gave?

My professor gave us this explanation from the textbook Introduction to Algorithms regarding the Master Method/Theorem: As a first example, consider $$T(n)=9T(n/3)+n.$$ For this recurrence, we ...
69 views

### How is the algorithm for recursively printing permutations of a set of numbers this equation our professor gave us?

I'm having a great amount of trouble understanding where my prof got $T(m, n) = n(T(m+1, n-1) + m+1 + n)$ if $n > 1$ as the recursive formula for the algorithm for recursively printing the ...
95 views

### Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
110 views

### Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
85 views

### Orange Juice, Milk, or Beer

Suppose that we have $n$ dollars and that each day we buy either orange juice for a dollar, milk for two dollars, or beer for two dollars. If $R_n$ is the number of ways of spending all the money, ...
168 views

### (CHECK) $n$-bit Strings Containing a Pattern

$$\text{\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and ...
72 views

### Number of times $g(p_1)$ occurs in $\sum_{d\mid n}g(d)$

$$g(n)=\begin{cases} 1 & \text{if }n=1 \\[10pt] \sum_{d\mid n,\ d\ne n} g(d) & \text{else} \end{cases}$$ How can I calculate $g(n)$ efficiently? I was trying to collect all the $g(p)$ ...
51 views

### Recursive algorithm

I am trying to understand how this works. My instructor is teaching his first class, in summer on top of that, and only had 3 slides on this and had to rush over it. His example is: ...
123 views

### Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
155 views

### Issue while applying Master Theorem

I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...