14 votes

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 ...
Steven's user avatar
  • 29.5k
10 votes

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 ...
nosyarg's user avatar
  • 232
7 votes

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 ...
NaturalLogZ's user avatar
3 votes
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 ...
Peter Cordes's user avatar
  • 1,055
3 votes
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 ...
Bernardo Subercaseaux's user avatar
2 votes

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 ...
NooneAtAll3's user avatar
2 votes

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 ...
Oscar Smith's user avatar
2 votes

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 ...
Darren Clark's user avatar
2 votes

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 ...
Yuval Filmus's user avatar
2 votes
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 ...
Discrete lizard's user avatar
  • 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 ...
Nathaniel's user avatar
  • 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 ...
orlp's user avatar
  • 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$, ...
D.W.'s user avatar
  • 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, ...
Massimo Cafaro's user avatar
1 vote

Find multiple order-statistics of an array

We would need to choose a tree data structure that preprocesses $n$ elements in $O(n)$ and processes each of the $m$ order-statistics queries in $O(log\ n)$, leading to a complexity of $O(m\ log\ n + ...
Kenneth Kho's user avatar
1 vote

Time complexity of search algorithms?

Let $A$ be a comparison-based search algorithm that takes a collection $C$ of $n$ elements and an element $x$ as input and outputs the position of $x$ in $C$, or reports that $x \not\in C$. Let $c(n)$ ...
Steven's user avatar
  • 29.5k
1 vote

Faster selection algorithm for small order statistics

Thanks to comment by @Yuval Filmus I get the idea. Basically we abuse transitivity that $x_j< x_{j+1}$ and $x_{j+1}< y_{j+1}\implies x_j< y_{j+1}$. Therefore we can conclude $(x_j,y_j)$ can ...
C.C.'s user avatar
  • 149
1 vote
Accepted

Minimum number of comparisons to find $2$nd smallest element

Assume that all elements are distinct (if not, replace each element with a pair $(element, position)$ and perform the comparisons lexicographically) and consider a rooted binary tree $T$ with $n$ ...
Steven's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Paul Schutte's user avatar

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