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
20 views
How to prove an algorithm with subroutines to belong to the polynomial time category using correct notation? [duplicate]
I'm having some trouble with writing my answer with the correct notation. I suppose I get the basic idea how to solve this and wrote down my answer but my gut tells me that that it's not ...
3
votes
3answers
55 views
Why is the running time of heapsort $O(n\log n)$?
Heapsort(A)
1 BUILD_MAX_HEAP(A)
2 for i=A.length downto 2
3 exchange A[1] with A[i]
4 A.heapsize=A.heapsize-1
5 MAX_HEAPIFY(A,1)
In the book on ...
2
votes
2answers
43 views
Average depth of a Binary Search Tree and AVL Tree
My professor recently mentioned that the average depth of the nodes in a binary search tree will be O(Log(n)) where n is the amount of nodes in the tree. I ended up drawing out a bunch of binary ...
0
votes
0answers
26 views
What is a good book to learn algorithm analysis and data structures for Ioi for a 15 year old with an ok math background? [closed]
I can code Python and I am now willing to learn algorithms and data structures and I need to know where to start.
0
votes
0answers
5 views
Complexity of comparing each element of an array with other elements [duplicate]
Imagine we have an array of objects with arbitrary length. What level of complexity (like O(n) or O(n*m)) will exist if we want to check each element of the array with another elements in the array ...
1
vote
1answer
25 views
How to determine approximability of a problem when we don't know how good a solution is?
As far as I have learned, an approximation algorithm for an optimization problem
Runs in polynomial time, and
Whose cost can be bounded by a function of input in terms of distance from the optimal ...
0
votes
1answer
35 views
Comparing different implementations of genetic algorithms
I am looking up some material for my thesis in CS (development of a module to integrate a genetic algorithm in a system developed by other students).
My actual current task is to make a comparative ...
-1
votes
1answer
43 views
What is the computational complexity of this problematic code we had
Some of my colleagues introduced some code into our codebase that was causing some serious performance issues. The feature they were implementing involved displaying data in a hierarchical fashion, ...
1
vote
2answers
42 views
Need help understanding how to find big theta of a snippet of code [duplicate]
Say I have a snippet of code:
...
0
votes
1answer
109 views
Algorithm for constructing BST from post-order traversal
Given a post-order traversal of Binary Search tree with $k$ nodes, find an algorithm that constructs the BST.
My Algortihm
Let $n$ represent the next element to be inserted.
Let $P(y)$ ...
1
vote
4answers
93 views
Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?
My question may actually be more broadly described as: can I use the fact that an algorithm is expected to return $(O(f(n))$ answers to show that it may never run better than $O(f(n))$? I would ...
2
votes
1answer
57 views
FPT algorithm for point line cover
In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.
The algorithm chooses each point p ...
0
votes
0answers
33 views
sheduling in parallel machines with machine delay and job constraints
Given m machines and n jobs ,we want to schedule jobs into machines ,such that lateness ie( idealCompletionTime- actualCompletionTime) is minimized .Also the machines are required to take a break ...
1
vote
0answers
60 views
Help understanding a problem with inclusion/exclusion
I am trying to understand how to use inclusion/exclusion in algorithm.
I think I understand the basic example of what the inclusion/exclusion principle is: the principle is in general illustrated ...
-1
votes
1answer
79 views
What is the size of an algorithm? [closed]
Question: Does the "size" of an algorithm typically refer to the number of its inputs, or its running time?
This seems an ambiguous term to me that I keep seeing in textbooks.
0
votes
0answers
11 views
how to calculate the average case efficiency of the improved bubble sort? [duplicate]
I already know that the average case efficiency for this algorithm is:
$\Theta(n^2)$.
But I want to know how to obtain this result.
This is the algorithm that I have:
...
0
votes
0answers
22 views
How to calculate runtime for FOR and WHILE loops? [duplicate]
While there have been many questions/answers around this on stackoverflow and wikipedia, I would like to have a clearer understanding on how to calculate it in layman's terms. I will say that, yes, ...
-3
votes
2answers
82 views
If the list lengths are m and n, why does the merge take O(m+n) operations?
If I have two sorted lists.
list A => 1 -> 2 -> 4 -> 11 -> 31
list B => 2 -> 31 -> 54
Now what should be the order of (sorted) merge and ...
1
vote
1answer
36 views
Algorithm Design Manual Question
In the book, Algorithm Design Manual by Steven S. Skiena, he states "Becoming familiar with many different algorithmic graph problems is more important than understanding the details of particular ...
1
vote
2answers
87 views
If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i]
Suppose that an algorithm uses only comparisons to find the $i$-th smallest element in a set of $n$ elements. Show that it can also find the $i−1$ smaller elements and the $n−i$ larger elements ...
1
vote
2answers
293 views
Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?
If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = \Theta(n^2)$, and $T(n) = \Omega(n)$, and all of those be ...
1
vote
0answers
56 views
DPLL time complexity analysis
Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
2
votes
0answers
48 views
How to chose optimal initial pheromone value for a ant colony algorithm
I am trying to develop an ant colony optimization algorithm that will minimize the electricity load shedding on a given graph. The graph has some supply vertices and some demand vertices. Supply ...
1
vote
1answer
32 views
Amortized analysis for doubling resizing array is ~3n
I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused:
Question 2: What if instead we decide to double the size of ...
1
vote
1answer
39 views
Lower bound on distinct element heapsort
I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS:
Exercise 6.4-5
Show that when all elements are distinct, the best-case running time of heapsort ...
0
votes
0answers
24 views
How to calculate a specific time complexity of inverse calculation of matrix? [duplicate]
I am a green-hand in calculating the time complexity. Given a calculation as follows:
\begin{equation}
\mathbf{x}=\mathbf{A^T}(\mathbf{AA^T}+\lambda\mathbf{I}_n)^{-1}\mathbf{b}
\end{equation}
where ...
3
votes
1answer
35 views
About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]
In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations:
$$\begin{gather*}
C_N = N + 1 + ...
5
votes
2answers
104 views
Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs
Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with ...
7
votes
2answers
259 views
n log n = c. What are some good approximations of this?
I am currently looking into Big O notation and computational complexity.
Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic ...
4
votes
1answer
83 views
What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms
I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms:
When the same heuristic ...
1
vote
2answers
33 views
Do Approximation Algorithms Analyzed in the Worst Case?
From wikipedia:
For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $ρ$-approximation algorithm $A$ is ...
3
votes
1answer
277 views
Is there a more efficient algorithm than backtracking/dynamic programming?
Consider the following game:
One day a castle is attacked at sunrise (by surprise) by n soldiers.
Each soldier carries a canon and a rifle.
The castle has strength s.
On the first day each ...
1
vote
3answers
222 views
If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?
I learned that recursive Fibonacci is $O(2^N)$.
However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or ...
4
votes
2answers
179 views
Good mathematical book on algorithms [closed]
I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very ...
0
votes
1answer
48 views
Merge two series of sorted number, one much longer than the other
This is the problem:
Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$
comparisons.
I have come up ...
0
votes
1answer
58 views
approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality
I have the following question for the travelling salesman problem:
The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph G. Instead of the traingle inequality, ...
5
votes
2answers
99 views
How to compare the time-complexity of an optimized algorithm with that of the original?
I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$).
I managed to reduce the ...
1
vote
1answer
68 views
0
votes
2answers
47 views
Running time analysis of a linear algorithm seems to me quadratic
I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I ...
0
votes
1answer
73 views
Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?
I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural ...
2
votes
2answers
64 views
What is the time-complexity of histogram computation?
Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.
Pseudocode:
...
2
votes
1answer
96 views
How can I compute the time complexity of this image processing algorithm?
Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing.
I simplified the algorithm ... so that we focus only on the problematic part.
...
2
votes
0answers
33 views
How to understand the formal analysis of quickselect? [closed]
According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof ...
3
votes
0answers
20 views
Running time for threshold function evaluation?
A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows:
$$f(x_1, ...
5
votes
4answers
102 views
Calculating the number of multiplications necessary to evaluate a polynomial
I was watching a lecture and got confused over a slide. This is what it says:
Consider a polynomial - first representation
$$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$
The ...
1
vote
2answers
23 views
Number of operations performed in increment operators [closed]
How many operations are performed in the following in order to get a running time function of an algorithm:
x = x + 1
x += 1
...
3
votes
1answer
41 views
Running time function for an algorithm with while and for loop
I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and ...
5
votes
1answer
78 views
How does Knuth measure the running time of this program?
I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand ...
1
vote
1answer
27 views
How to test image segmentation algorithms? [closed]
What would be an ideal environment/manner to judge the effectiveness of multiple segmentation algorithms? The goal is to determine which algorithms provide the best results for pre-clinical imaging. ...
1
vote
1answer
28 views
Extra space of MergeSort [duplicate]
Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
