# Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

1,935 questions
Filter by
Sorted by
Tagged with
69 views

### Proving Quicksort is $O(n^2)$

So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$. I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following ...
171 views

### Finding an algorithm to return the $\log n$ largest element in an array

I have just proved that for every $\alpha, \beta>0 : (\log n)^\alpha=O(n^\beta)$. Now, given an array of $n$ elements, I want to find an efficient comparison based algorithm for finding the $\log n$...
27 views

147 views

### How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
142 views

### Single-source shortest path problem with diameter

Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and ...
17 views

### largest gcd of an array after a few operations

consider we have n bags of random amounts of coins. given k extra coins, the question is to find the largest gcd that can be ...
41 views

### Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$

Given a circle with $n$ equal segments. On each segment there is an integer. We want select segments at equal distance, maximizing the sum of integers on selected segments. I have an algorithm with ...
53 views

35 views

### search + filter best data structure

What data structure is best to use to facilitate a text search and a filter (by tag, for example) Lots of sites support something similar: on StackExchange you can write in the search box ...
50 views

### Asymptotic bounds of the following operations

I have a very simple question about the best possible big-O bounds for the following data structure: It starts out empty When you add an element, it is inserted, and the index it was at is associated ...