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

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

*O*(*nlogn*). How does linearity of expectation allow us to show this?

Let, *x*1 < = *x*2 < = *x*3....... < = *xn*

and

*p*1 + *p*2 + *p*3 + ....... + *pn* = 1

We all know that average of *x*1, *x*2, *x*3......., *xn* is in [x1,xn] and it is easy to understand.

In a contest, I assumed Expected value = *p*1 * *x*1 + *p*2 * *x*2 + *p*3 * *x*3 + ....... + *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 dimas.kovas.

```
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 ?

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2020 01:24:37 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|