# Tag Info

### Time Complexity of Linear Search vs Brute Force

Time complexity is expressed as a function of some parameter, which is usually the size of the input. The combination lock is not a perfect analogy as it is not immediately clear what the input would ...
• 29.5k

### What is the name of this search algorithm?

I do not think there is a name for that particular algorithm, but I think it will achieve similar performance to much simpler parallel algorithms for this task. In general when designing parallel ...
• 232

### Time Complexity of Linear Search vs Brute Force

You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying ...
• 606
Accepted

### What is the name of this search algorithm?

It's a parallel linear search, with an over-complicated way to divide up the array into a power-of-2 number of chunks. (Since you only split in half with multiple levels of recursion, instead of the ...
• 1,055
Accepted

### Any text similarity algorithms for substrings?

It seems that in your context there can be prefixes or suffixes added to the substrings you care about, so for example you want the strings $w$ and $\alpha v \beta$ to be similar if $v$ and $w$ are ...

### Find median in a sorted matrix

Probably main problem I see is recursion being made on values we put $mid=\frac{min+max}{2}$ If number of smaller elements than mid is lower than $\frac{n^2−1}{2}$, then we put min=mid+1. Otherwise ...
• 123

### Find median in a sorted matrix

Is the time complexity analysis correct? no. you changed what n means when you included the master theorem. The runtime of this algorithm is ...
• 119

### Time Complexity of Linear Search vs Brute Force

They are both correct, but the N is different. Algorithmic brute force: Inputs: X: Size of each combination element N: Number of combination elements Algorithm generates all possible combinations and ...

### Graph labyrinth solving sequence

Let $G_1, \dots, G_m$ be an enumeration of all strongly connected directed graphs on at most $n$ vertices in which every vertex has out-degree 2 (the corresponding edges labelled $a,b$). The algorithm ...
• 277k
Accepted

### Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

The usage of "within" is a bit confusing, but I think it means the space complexity is never smaller than the time complexity divided by a factor of $b$. The space complexity of an algorithm ...
• 8,248
1 vote

### Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

It depends on the order of the children. It is usually the case that children in rooted trees are browsed from left to right. Also, if the DFS is written recursively, then this is indeed the correct ...
• 15.6k
1 vote

### How to find largest caterpillar in a tree

Hint: the heaviest caterpillar that can be formed by a path starting at a node and moving strictly downward in the tree (its down-weight) is the down-weight of the heaviest non-leaf child if it ...
• 13.4k
1 vote

### Maximum of a tritonic array

You can't. It's not possible to do this in $O(\log n)$ time. Consider the following two possibilities for the tritonic array: We have an array $A^1$ that contains the values $1,2,3,4,\dots,n$, ...
• 159k
1 vote

### Find median in a sorted matrix

The algorithm proposed by Mirzaian and Arjomandi (A. Mirzaian, E. Arjomandi, Selection in X + Y and matrices with sorted rows and columns, Information Processing Letters, Volume 20, Issue 1, 1985, ...
• 4,247
1 vote

• 29.5k
1 vote
Accepted

### Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?

I suspect you might be interested in Class Hierarchy Analysis (CHA), Rapid Type Analysis (RTA), or Variable Type Analysis (VTA). These are three methods for efficient construction of a call graph in ...
• 159k
1 vote

### Need help with adding elements to hashtable with linear probing

It is the hash function h(k) that determines the position. They don't specify the hash function, but instead they give the value to which h(k) evaluates for both tables. The hash function is usually a ...
• 111

Only top scored, non community-wiki answers of a minimum length are eligible