# Tagged Questions

22 views

### Big O complexity of the partition function derived from this code?

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree. So far, I've figured out that ...
17 views

### Complexity of FFT Algorithm

OkayI am using iterative FFT algorithm and I have found that since there are 2N computation per stage and there are logN stages the complexity should be O(2NlogN) I can reduce the number of ...
30 views

### Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
30 views

### Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
131 views

### How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
123 views

### find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
240 views

### Big Oh Notation for a Recursive Algorithm

I have a question that I'm unsure of: Express the complexity of the following method using big-O notation. You must explain how you arrived at your answer. What value is returned by the call ...
152 views

### Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where e is the natural logarithm}$$ To solve this and find a Θ bound, i tried the following: I ...
92 views

### The use of master theorem appriopriately

I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is: $$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$ Can i use the master theorem in that relation? If ...
793 views

### Solving a recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n) = aT(n/b) + f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master ...
184 views

### Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
66 views

### Confusion related to time complexity of fast Fourier transform

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT. It says that lets say I have a polynomial of ...
434 views

### Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
### Worst case of Heapify is $\Omega(n \lg n)$
Worst case of Heapify is $\Omega(n \lg n)$ I know that Heapify is $\Theta(\lg n)$, but I don't know if $\Omega(n \lg n)$ is equivalent. Thanks.