# Tag Info

Accepted

### Algorithm for finding two smallest numbers in an array

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 ...

### Should you use Genetic algorithm for an extremly large unstructured search space?

No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying ...

### Searching through a heap complexity

You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is ...
Accepted

### Searching the space of permutations

Consider the following set of $n$ orders, which I give for $n = 6$: $$123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465$$ Hopefully the generalization to arbitrary $n$ is clear. If you never ...
Accepted

### Finding an element in a sorted array with at most three queries to larger elements

If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$ If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can ...

Accepted

### Efficiently count frequency of n-grams at start of words

There is a 11.881.376 times faster method. Instead of for every 5-gram looping over the entire dictionary, loop over the dictionary once, and for every word determine with what 5-gram it starts and ...

### Solving cycle in undirected graph in log space?

The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number ...

### Algorithm for finding two smallest numbers in an array

Hoare's algorithm, which Wikipedia calls Quickselect, can find the $k$ smallest elements of an array in $O(n)$ time for any fixed $k$. It is a modified Quicksort algorithm that sorts the array but ...
Accepted

### Efficiently locating the maximum value in interval over large amounts of data points

This can be solved with a balanced binary tree. Each such query can be answered in $O(\lg n)$ time. Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-...

### Heuristics for the $n$-puzzle

First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to ...
Maybe it depends on what it means by solving an optimization problem. If it is to find "how big is the biggest $f(x)$", then the answer is no (see the answer of @David Richerby). If it is to find "the ...
To reformulate the question, there is the following problem: given an array of numbers, find an index in the array that is a local maximum, meaning the value at that index $\ge$ the values at adjacent ...