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
13 views
How does the search for the lowest link in Tarjan's SCC Algorithm work?
Wikipedia describes Tarjan's SCC algorithm the following
...
0
votes
1answer
21 views
What is the time complexity in big-O notation of Algorithm X?
Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that solves the NP-complete problem exact cover (EC). (It actually finds all solutions to EC.)
I do not ...
3
votes
1answer
35 views
On complexity of the sieve, start crossing at the square of p - Part II
Ok, this is a follow up question to this, about the Erathostenes Sieve.
If we look at this paper (page 3, footnotes), the author says:
If we start crossing off at $p^2$ rather than $p$, the number ...
0
votes
1answer
41 views
what is the Recent Nature Inspired Algorithm for Optimization?
I'm into designing a recommender system for movie database and for effective optimization.I suggested the idea of using particle swamp optimization ,but my professors need recent algorithms,can any ...
1
vote
0answers
25 views
Use of Mizar for algorithm specification and automatic analysis and discovery of algorithms?
Is it possible to use Mizar Mathematical Library for the specification of algorithms at the same detalization level as the implementation of the algorithm in industrial programming language? Mizar ...
4
votes
1answer
35 views
On complexity of the sieve, start crossing at the square of $p$
This question is about a common optimization in the basic sieve of Erathostenes.
If we look at this paper (page 3, footnotes), the author says:
If we start crossing off at $p^2$ rather than $p$, ...
2
votes
0answers
54 views
What is the Big-Oh asymptotic complexity of learning in Random Forests?
Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right.
CART (Classification and Regression Trees) uses the Gini index for ...
1
vote
1answer
40 views
Interesting problems that can be solved with algorithms [closed]
I need to write a blog post on a problem that can be solved algorithmically. I need to do two things:
1) I need to decide what the naive brute force method would be and touch on it's time and Space ...
0
votes
0answers
29 views
Boys And Girls Problem. How to prove that the algorithm is correct?
Given that, there are 10 children standing in a circle, 8 of them stand next to a boy, and 4 of them stand next to a girl.
If 7 boys and 3 girls stand in the following order: GBGBGBBBBB, then 8 ...
2
votes
1answer
16 views
What is the time complexity of binary sum (recursion) [duplicate]
Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions.
There is an ...
3
votes
2answers
26 views
Can I notate time complexity depending on the result of an algorithm?
I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(...
3
votes
0answers
70 views
FPT: Dominating Set on Planar Graphs (average degree is known)
I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this:
Dominating Set on Planar Graphs
Instance: A planar graph G and an
integer ...
1
vote
1answer
34 views
How to solve this asymptotic complexity problem?
The increasing order of following functions in terms of asymptotic complexity is:
(A) f1(n) < f4(n) < f2(n) < f3(n)
(B) f1(n) < f2(n) < f3(n) < f4(n)
(C) f2(n) < f1(n) < f4(...
1
vote
1answer
56 views
Prove correctness of iterative LCM algorithm
I have been trying to prove the following algorithm, without success.
Here is the C-Style pseudocode:
...
2
votes
1answer
145 views
2
votes
1answer
49 views
Big O complexity of algorithm with a nested for loop only running once
I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^...
0
votes
1answer
41 views
Hashing Probabilities
I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a ...
1
vote
0answers
64 views
Run time of Dijkstra's compared to Kruskal's algorithm using union-find
I am dealing with the following statement:
the run time for Dijkstra's on a connected undirected graph with positive edge weights using a binary heap is $\Theta$ of the run time for Kruskal's using ...
7
votes
2answers
194 views
Can we do better than $O(n\log n)$ building a balanced binary tree?
I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking?
Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-...
4
votes
1answer
63 views
Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?
If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to ...
1
vote
1answer
44 views
Help with a difficult expected runtime recurrence
I developed an algorithm and have a recurrence for its runtime; I want to show the expected runtime is $O(\sqrt{n})$.
At each iteration $i$, I have a random variable $k_i$ that is equal to the number ...
3
votes
2answers
81 views
Number of balanced binary trees (The Art of Computer Programming)
In the section 6.2.3 (Volume 3) Donald Knuth says:
... we can ask about the number $B_{nh}$ of balanced binary trees with $n$ internal nodes and height $h$. It is not difficult to compute the ...
4
votes
1answer
70 views
Skip List randomization complexity
I understand the basics of Skip Lists and their implementation also the basic Search Insert ...
0
votes
0answers
34 views
What is the algorithmic complexity of DFS under the cache oblivious model?
Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size &...
-1
votes
0answers
35 views
Determing the Big O for recursive functions [duplicate]
$T(n) = aT(n/2)+n$ for $a= 1,2,3,4$
For the case a=2 I got $O(n*log(n))$ which is I assume right. But what about a=3 and a=4?
1
vote
1answer
52 views
What is the time complexity of an algorithm that calls a polynomial time algorithm?
I'm having a difficult time understanding time complexities of algorithm. I know that a polynomial time is of the form O(n^m) where m is a constant. Consider the following case where A is a list of ...
4
votes
1answer
62 views
Analysis of a randomized algorithm for independent set construction
Suppose that $G = (V,E)$ is a 3-regular graph on $n$ vertices and $m$ edges. Below I propose a randomized algorithm for obtaining an independent set for $G$.
Step $1$: Delete each vertex (...
0
votes
1answer
59 views
Using AI / Machine learning to find the most time and space efficient solutions to an algorithm [duplicate]
As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms.
Is it forseeable in the future that we have languages or techniques such as AI/...
1
vote
1answer
56 views
Average number of collisions before successful insertion into hash table
I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.
I was thinking that since it is a linear probing and ...
2
votes
1answer
53 views
Shunting Yard Algorithm extension and AST generation
Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM ...
0
votes
1answer
28 views
Amortized analysis for dynamic array - how to come up with a potential function?
I learned about amortized analysis and the potential method, I also
leaned an example of a binary counter which I think I understand well.
In the case of the binary counter I understand the choice of ...
1
vote
1answer
70 views
Correctness proof: 2-approximation of greedy matching-algorithm
Input: number of edges and vertices, and array of all edges in graph.
Output: array of edges that construct a matching, so that:
$$\frac{\text{the number of edges in this matching}}{\text{the number ...
0
votes
1answer
62 views
Question regarding coin change algorithm (DP and greedy)
The question goes something like this:
Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy ...
1
vote
1answer
28 views
Does the running-time of this push-relabel algorithm become zero if there are many edges?
According to the Wikipedia page on the Push-relabel maximum flow algorithm:
Subcubic $O(|V||E| \log\frac{|V|^2}{|E|})$ time complexity can be achieved using dynamic trees, although in practice it ...
0
votes
0answers
28 views
Finite State Automata Implementation [duplicate]
i already search about FSA implementation, but what i found is FSA implemented to something like fending machine. I want to ask about FSA, it was possible Finite State Automata implemented into a ...
1
vote
1answer
74 views
How can you determine what set of boxes will maximize nesting?
I'm trying to find a dynamic solution to the nesting boxes problem.
You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can ...
2
votes
1answer
41 views
Calculate Complexity, loop incremented by log(k)
I'm preparing for an exam, and I ran across the following algorithm:
...
0
votes
1answer
47 views
What is the time complexity (upper bound) for this simple recursive function? [duplicate]
So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows:
...
0
votes
1answer
48 views
Triple nested loop where outer and inner loop are dependent on n
I am trying to count the exact/total number of iterations these nested for-loops are executed:
...
0
votes
1answer
38 views
Which of these simple data structures is most efficient when implementing a Dequeue?
A deque is a double ended queue of course. So if I can either use 2 stacks, or 2 queues, or 1 stack and 1 queue, which two would I use to have the fastest implementation? Can we derive the complexity ...
0
votes
1answer
35 views
How long will selection sort and merge sort take to sort a certain number of items?
I am dealing with a sample exam question that I cannot understand which is as follows:
Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. Estimate ...
0
votes
1answer
62 views
How can you find the total possible solutions to a tiling problem?
So I've heard of tiling problem but I've never done one before so I was hoping someone could help me with this basic one.
You'r basically given a surface that is 4 units by w units where w >= 1.
...
0
votes
1answer
57 views
How to rank these functions in increasing order of complexity [Algorithms]? [duplicate]
I have the following functions:
What is the correct order of these functions in increasing complexity?
I could always start entering values in these functions and check the corresponding output to ...
2
votes
1answer
244 views
Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?
I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something.
The analysis goes as follows:
Fix a min cut $(A,B)$.
Let $k$ = # of edges crossing $(A,B)$ , ...
0
votes
0answers
23 views
Need confirmation for and answer related to algorithm notations(ϴ,O and Ω) [duplicate]
In my class we have to answer a question:
Having this pseudocode:
XPTO(n)
sum = 0
if even(n)
for i=1 to n
sum = sum + i
else sum = 0
and knowing that ...
0
votes
2answers
57 views
Approximating the runtime of a practice problem [duplicate]
I'm studying for an algorithms exam and came upon the problem :
...
1
vote
1answer
88 views
Height and depth of every node in Path Compression
If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a find operation, how would the depth and height of every node change after the find ...
0
votes
0answers
60 views
Analysis of Union-Find(Disjoint Sets)
I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data ...
-1
votes
1answer
44 views
Quadratic algorithm for Matrix Chain Multiplication [closed]
I have an algorithm that supposedly solves the matrix chain multiplication problem in $O(n^2)$ time. I have tested it only on trivial cases and they turned out to be correct.
By no means, am I a ...
0
votes
2answers
60 views
