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} \...


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 ...


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 ...


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 ...


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.


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$.


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{...


Only top voted, non community-wiki answers of a minimum length are eligible