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

2 | jiangly | 3669 |

3 | ecnerwala | 3654 |

4 | Benq | 3627 |

5 | orzdevinwang | 3612 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | jqdai0815 | 3532 |

9 | Radewoosh | 3522 |

10 | gyh20 | 3447 |

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

1 | awoo | 161 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 153 |

5 | -is-this-fft- | 148 |

5 | SecondThread | 148 |

7 | Petr | 147 |

7 | atcoder_official | 147 |

9 | TheScrasse | 145 |

10 | nor | 144 |

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 09:01:09 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|