New answers tagged

0

Define S(n) = T(2^n), write down a recursion formula for S, solve it using the master theorem, and then let T(m) = S(log m). Or calculate T(n) for n = 3^0, 3^2, 3^6, 3^14, 3^30, 3^62 etc. without the master theorem, guess a formula for T(3^(2^k-2), and prove it. Let D log 3. If T(1) = c, then T(9) = 4T(1) + (log 9)^2 = 4c + 4D^2. T(3^6) = 4T(9) + 36D^2 = ...


0

Didn’t read your solution. You have n slots, alpha x n are occupied, (1-alpha) n are empty. Every hash code defines a sequence of indices that will be checked until either the item or an empty slot is found. Let E(Alpha) be the expected number of slots visited, then E(alpha) = 1 x (1-alpha) + alpha (1 + E(alpha)) or E(alpha) = 1 / (1-alpha). With your alpha =...


0

Master Theorem is for Dividing and Subtracting Function. The Master Theorem at it's core don't discuss Square Root Function. Although, some Manipulations can be done. But for the sake of simplicity, solving by Substitution Method Given, $T(n)=4T\bigg(\frac{\sqrt n}{3}\bigg) + (\log(n))^2$ $T(n)=4T\bigg(\frac{n^{1/2}}{3}\bigg) + (\log(n))^2$ $T(n)=4\bigg(4T\...


2

You can not do better than $n-2$ in the worst case. You can show this using an adversarial argument. Suppose the array is $A = [1,2,3,\dotsc,n]$. There is no index in the array that satisfies that $A[i-1] \geq A[i] \leq A[i+1]$. Therefore, the answer is trivially no. For the sake of contradiction assume that there is an algorithm that solves the problem in ...


0

We can use Master Theorem to solve this : If a Recurrence Relation is of the Form $$T(n)=aT\bigg(\frac{n}{b}\bigg)+{n^k}({\log(n)})^p$$ Then, as per Master Theorem, we have Six Conditions depending on value of $a,b,k$ and $p$ If $\log_ba>k$ Answer is $\theta(n^{\log_ba})$ If $log_ba=k$ and $p>-1$ Answer is $\theta({n^k}({\log(n)})^{p+1})$ If $log_ba=...


1

If someone is not aware of method to solve this recurrence, then We can solve this by Substitution Given, $$T(n)=2T(\frac{n}{2})+1$$ Now, going by relation, $$T(\frac{n}{2})=2T(\frac{n}{4})+1$$ We will Substitute this in Original Recurrence Relation Therefore, $$T(n)=2T(\frac{n}{2})+1$$ $$T(n)=2 \Biggl(2T(\frac{n}{4})+1\Biggr) + 1$$ $$T(n)=2 \Biggl(2T(\frac{...


1

Let's consider the swaps performed by insertion sort. In the $i$-th iteration, insertion sort repeatedly swaps the element $x$ originally in $A[i]$ with some element $y$ originally in $A[1:i-1]$ until the subarray $A[1:i]$ is sorted. Then, since we must have $x<y$ for the swap to occur, we have that each swap induces an inversion in the original array. ...


1

Number of permutations of length $n$ with $k$ inversions refers to so called Mahonian numbers $T(n,k)$ who are generated by coefficients from expansion $$\prod\limits_{i=0}^{n-1} (1 + x + ... + x^i)$$


1

For example, if to place the minimal element into the maximal position, you'll get $n-1$ inversions: $${2,3,4,5,1}$$ For more information please see here.


0

At every "phase" it will do that much comparisons. Since there are $n$ such "phases", the number of comparisons can be worst case $\Theta(n^2)$


1

Assuming $\log=\log_2$, we have $$2^{n+\log_2 n}=2^n \cdot 2^{\log_2 n}=n \cdot 2^n$$ where we used main property(or definition) of $\log$: $a^{\log_a b}=b$, for appropriate $a,b$.


2

We introduce a weight measure for $S$, a set of numbers with respect to its average, namely: $w(S) = \sum_{s\in S} |s-avg(S)|$. The measure $w(S)$ expresses the total distance to the average. Based on this weight we will prove the number of iterations is in $O(\log\ n)$. If we apply one iteration of your described algorithm on a set $S$ we obtain either the ...


12

It's an abuse of notation. $O(n)$ is a set of functions. So $O(n)*O(n)$ is not really defined. $O(n)\times O(n)$ is defined, but it is defined as cartesian products of the set of functions in $O(n)$ by itself. This is probably not what you are after. Within the context of algorithm analysis most would interpret $O(f)*O(g)$ to mean that we do some operation ...


20

Yes, you can and yes, it is. Considering, for example, the non-negative case, we have a more general property: $$O(f)\cdot O(g) = O(f\cdot g )$$ Let's take $ \varphi \in O(f) \cdot O(g) $. Then we have $\varphi = \varphi_{1} \cdot \varphi_{2}$ where $$\exists C_{1} > 0, \exists N_{1} \in \mathbb{N}, \forall n > N_{1},\ \varphi_{1} \leqslant C_{1} \...


Top 50 recent answers are included