# Tag Info

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})+1T(n)=2 \Biggl(2T(\frac{n}{4})+1\Biggr) + 1T(n)=2 \Biggl(2T(\frac{...