In computer science, the randomized quicksort algorithm has expected runtime O(nlogn). How does linearity of expectation allow us to show this?

Let, x1 <  = x2 <  = x3....... <  = xn

and

p1 + p2 + p3 + ....... + pn = 1

We all know that average of x1, x2, x3......., xn is in [x1,xn] and it is easy to understand.

In a contest, I assumed Expected value = p1 * x1 + p2 * x2 + p3 * x3 + ....... + pn * xn is in [x1,xn] regardless how probability is distributed that means the sum of probability can be 1 in many different ways.

My assumption was right and got ac. I'm interested to know the proof.

TIA

Question 01:

Is there any technique where generating random number within a range is equiprobable ?

Question 02:

What is the extra advantage of the following method 02,03,04 ?

srand(time(NULL);

//Method 01: general approach

int myrand(int mod){
  return rand()%mod;
}

//Method 02: Taken form red coder submission.

int myrand(int mod) {
    int t = rand() % mod;
    t = (1LL*t*RAND_MAX + rand()) % mod;
    return t;
}

//Method 03: Taken from red coder submission.

int myrand(int mod) {
	return (int) ( (((double) rand() / RAND_MAX) * (mod) ));
}

//Method 04 : Taken from red coder submission.

inline int myrand(int mod) {
	return (((long long )rand() << 15) + rand()) % mod;
}

Updated : Idea from diko.

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt(seed);

int myrand(int mod) {
    return mt()%mod;
}

The problem was set in acm icpc preliminary contest 2017 in Dhaka site. Problem Link : E.Anti Hash

Problem is : you will given a string S of length N consisting of lowercase letters (a-z) only.Also given a base B and mod-value M for doing polynomial hashing. Note : B and M are both prime.

Your task is to find another string T, satisfying all of the following constraints: Length of T is exactly N. T consists of only lowercase letters (a-z). T and S have the same hash value that means, collision happens. For hashing in both case you have to use B and M.

Any idea? Thanks in advance.

If a String is : "Topcoder" and all of it's suffix are :

r,er,der,oder........pcoder,Topcoder

Now consider c++ code:

std::string str = "Topcoder";
const char* pointer = &str[1];
cout<<pointer<<'\n';

Output is: opcoder

What is the complexity of generating of above suffix upto 1 index of length 7? Linear or Constant ?

Is 10^9 computation is possible before 2.00 seconds? If not possible,how my solution works of following problem? Problem link: http://codeforces.com/problemset/problem/851/C Submission: http://codeforces.com/contest/851/submission/30089349

Chek the link: https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/