All Questions

Filter by
Sorted by
Tagged with
3
votes
3answers
106 views

How good (or bad) is my makeshift PRNG?

Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I ...
2
votes
2answers
636 views

How to determine seed collision probability in a PRNG?

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...
3
votes
1answer
2k views

How to understand the analysis of expected running time of randomized quick-sort in this paper?

I'm learning the book named Data Structures & Algorithms in Python. On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me ...
2
votes
3answers
3k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
1
vote
3answers
297 views

What is the time complexity of this аlgorithm? O(n * r)

Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function ...
2
votes
1answer
126 views

What is the Expected run time of an algorithm that randomly generates N unique strings of length D?

I was trying to rigorously/mathematically analyze the runtime of the following algorithm: ...
0
votes
1answer
2k views

Comparing random access and sequential access

Assume that we choose randomly $k$ distinct numbers $N_1$, $\dots$, $N_k$ in $\{1, \dots, k\}$ and we have a file of $k$ parts. We have these two cases : We read (or write) sequentially from part $1$ ...
33
votes
2answers
1k views

How asymptotically bad is naive shuffling?

It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly: ...