2

https://www.bigocheatsheet.com considering finding (Access) the position of the element before insert as separate operation. Array: Access - O(1) // we can get the element by index directly Insertion - O(n) // in the worst case we need to resize the array to have a space for the new element Linked list: Access - O(n) // we need to reach the element ...


1

The probability $1/i$ is correct, since it refers to the relative order of $a_1,\ldots,a_i$ before sorting the first $i-1$ elements. However, the argument seems wrong. The relevant probability is not $p_i(k)$, but rather $q_i(k)$, which is the probability that $a_i$ is the $k$'th smallest element out of $a_1,\ldots,a_i$ (before sorting). This probability is ...


1

Let us assume that we are given a real number $x$ and a list of $n$ distinct real numbers. The linear search algorithm, described below, linearsearch(x, a1,a2,...an): i:=1 while(i<=n and x not equal to ai): i:=i+1 if i<=n: loc:=i else: loc:=0 locates $x$ by successively ...


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