Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.

0
votes
0answers
21 views

Minimal hashing function for integers that satisfy specific constraints

I'm looking for a kind of way to create a minimal perfect hash function given a set known integers. More specifically, I have M numbers within the range 0-N with N > M. Does it exist a way to create ...
1
vote
0answers
37 views

Given max-flow determine if edge is in a min-cut

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
-1
votes
0answers
36 views

An infinity family of graphs for which an heuristic solution for vertex cover works [on hold]

Suppose we do a DFS on an undirected, connected graph G.then we find a set of non-leaf vertices that forms a vertex cover of G. What could be an infinite family of graphs for which this heuristic ...
0
votes
1answer
44 views

Complexity of finding a majority element

I was given a question that is stated that; Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection ...
0
votes
1answer
24 views

Determining an appropriate number of buckets for a hash function

I would like to select an appropriate number of buckets in my hash table for this scenario: A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed ...
2
votes
0answers
19 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
0
votes
0answers
21 views

between hoare and lomunto quicksort which give better cache performance?

between hoare and lomunto quicksort which give better cache performance ? we know that in hoare quicksort we move the pointer i,j in different direction but in lomunto quicksort we move i,j in same ...
2
votes
1answer
23 views

minimum number of nodes that traverse all the graph

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
-4
votes
0answers
15 views

Complexity of CYK algorithm [on hold]

What is the Big O complexity of the CYK ( Cocke–Younger–Kasami ) algorithm as a function of the size of grammar G?
2
votes
1answer
19 views
0
votes
1answer
59 views

Calculate the average length of the linked lists in a hash table

I am learning hash tables, and I would like to know how to determine the average length of the linked lists. For example: A hash table holds about 10,000 employee records. Each record is indexed by ...
0
votes
0answers
24 views

If you have two recursive calls in a function and one terminates before the second how do you calculate the time complexity? [duplicate]

Suppose you have a function which calls to itself twice. So both go down recusively until they reach some condition. But one of them will go less times than the other. For example one would call ...
1
vote
0answers
12 views

Find $b$-th bit of a number $n$, with sign [closed]

Let $n\in\mathbb{Z}$ and $0\leq b\leq63$, $b\in\mathbb{N}$. Find the $b$-th bit for the number n on it's $64$ bit representation with sign. and $T$ be the number of test cases. This is my attempt: <...
1
vote
0answers
10 views

How to use HITS algorithm to rank pages

I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this ...
1
vote
0answers
30 views

Upper bound on the average-case runtime of shell sort

I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases. I want to know the upper bound complexity in average cases, so I write ...
0
votes
0answers
12 views

Forming an algorithm for assigning priority weights

I'm trying to develop/research an algorithm in which I can use to assign weighted values (priorities) to a list of jobs that need to be done. I've come up with some kind of arbitrary weights, but I'm ...
0
votes
0answers
18 views

Why the answer is 26 for this code? [migrated]

public class Program { public static void main(String[] args) { int x=1; for(;x<6;x++) x=x*x; System.out.printf("%d",x); } } I ...
1
vote
1answer
42 views

Finding the Kth largest element can be optimized to O(n) only if k is a constant?

There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$. ...
1
vote
2answers
50 views

What is the real reason that Bubble Sort runs at O(n) in best case?

In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...
1
vote
1answer
38 views

Adding two running time from a function

I have a method Func() that has two inner methods Func1() and Func2(). ...
2
votes
0answers
32 views

Theoretical performance measures other than worst case

Suppose that $P \neq NP$, and $P = BPP$. Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
0
votes
1answer
51 views

Hiring problem from CLRS

Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions. However, for Exercise question 5.2-2 my solution deviates from the one given in the ...
1
vote
2answers
25 views

Deriving the average depth for a randomly generated binary search tree

If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken ...
0
votes
1answer
19 views

Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm

For the following algorithm, $X\leftarrow \{(i, n - i) | i = 1, ..., n- 1\}$ while $\max_{(a, b)\in X}b > 0$ do $\quad X \leftarrow \{(|a - b|, \min\{a, b\})|(a, b) \in X\}$ ...
0
votes
0answers
23 views

Iterative Backtracking Method to Recursive Method

I have the following algorithm as a solution to a maze given the maze as a graph, the point of entry and the point of exit. I am attempting to transform this method into it's recursive equivalent. <...
1
vote
2answers
49 views

Is the runtime of binary search big omega of logarithm of n?

My question is that can we say that runtime of the binary search is $\Omega(\log n)$? I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
0
votes
0answers
23 views

Perfectly Imperfect Masterpieces

I was looking through this problem and I think I understand how the implementation works, but do not understand how I am supposed to get the algorithm and analyze its time complexity. I am new to ...
-1
votes
2answers
30 views

Using Iterative method to find recurrence relation vs Master Theorm

I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem. $$\begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &=...
0
votes
0answers
8 views

Potential function for ski rental problem

I am trying to understand potential function method used in List Reorganising problem (typically Move-To-Front method) and I wanted to create another potential function for ski-rental problem to show ...
0
votes
0answers
27 views

Big-O of a recursive function [duplicate]

just wondering, what's the big o of this function, let say the initial value of the parameters is as following: ...
0
votes
0answers
5 views

Does ignoring noise points once found in DBScan make the output dependent on the input order?

When looking at DBScan pseudocode from multiple sources like this one one may notice that once a noise point is found it is never again considered as a member of a cluster. Can't it be that a point ...
0
votes
1answer
37 views

How do I determine the basic operation of this algorithm?

Admissions: Yes, this is a homework assignment. No, this is not me trying to outsource my homework to the internet. I am honestly fazed by my teacher's explanation of the "basic operation", and the ...
0
votes
2answers
51 views

Understanding how quicksort operates

I am having a hard time understanding the quick sort partition operation. I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand ...
2
votes
0answers
33 views

how to find the depth of a concurrency bug

How to find the depth of a concurrency bug The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug ...
1
vote
0answers
51 views

Clock page replacement policy vs LRU page replacement policy, is Clock more efficient?

I'm currently learning about database systems and they mention a buffer management system which brings in pages from disk to memory. This buffer manager allows higher layers to operate as if the ...
1
vote
2answers
75 views
1
vote
1answer
41 views

Can both $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$ happen at once?

For which case are both $f(n) \ne O(g(n))$ and $g(n) \ne O(f(n))$ true? I have following answer to this which I could not understand: Sometimes true: For $f(n) = 1$ and $g(n) = |n \sin n|$ it is ...
1
vote
1answer
68 views

How many rotations after AVL insertion and deletion

Is it true that inserting an element to an AVL tree requires $O(1)$ rotations? How many rotations, does deletion from AVL require? I've searched for these two questions with no luck so far.
1
vote
0answers
28 views

What can be a Zero Knowledge Proof of a working SAT Algorithm?

Me and my colleague are exploring new ideas to solve SAT efficiently (i.e. in polynomial time) and it's the case that there is a candidate algorithm. Unfortunately, neither of us can write scripts ...
1
vote
1answer
75 views

Answering questions about the recurrence of certain aspects of an algorithm

I am thoroughly confused by a problem that was brought up in class: Given the following pseudocode for a function RANDOM which generates a random number based off of recursion: ...
1
vote
0answers
46 views

Algorithms that solve a practical problem but have not been proven correct

Are there any known famous and usable algorithms that seem to solve some famous problem but which haven't been proven to be correct?
0
votes
1answer
21 views

is the alignment between two sequences of points with 'no cross line' constraint an NP problem?

Given two sequences of points(i.e. ordered points), connect the points in seq_A with the points in seq_B according to some rules. A point could be connected to 0, 1, or many points in the other ...
0
votes
0answers
47 views

What is the time complexity of this power algorithm?

I'm trying to learn more about time complexity of algorithms on my own, but it comes very confusing when recursion gets into it. The power function calculates $x^...
1
vote
1answer
34 views

What's the output of this algorithm?

Given the question below: Consider that, on the procedure below, the variable X is defined globally and the parameters of the vr function are passed by value ...
0
votes
0answers
25 views

Algorithm Fragment Analysis

I am not exactly sure what this question is asking: Provide an asymptotic notation for the sum obtained as the result of the following program fragment: ...
0
votes
0answers
31 views

Sorting an array consisting random numbers

In this sorting animation, I saw that heap sort and merge sort works best for an array containing random numbers. But, what about if we compare these sorting algorithms with Radix and introsort? In ...
2
votes
1answer
52 views

Is there a measure of space usage over time?

We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space. However, I feel this does not capture the full story. Say we ...
2
votes
1answer
34 views

Selection Sort Analysis

I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers): ...
2
votes
2answers
69 views

Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck: $$T(n) = 2T(n/3 + 1) + n$$ I have checked out this link here on time complexity on cs.stackexchange ...
1
vote
0answers
41 views

Misunderstand a algorithm

I fail to understand a algorithm, basically the matrix multiplication portion. I can explain the unknown terms. At line no: 4 j will be 1,2,3,....,15. When ever new object is observed a value ...