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.

learn more… | top users | synonyms

0
votes
1answer
25 views

CPU influence in speed of a task with inefficient Algorithm [on hold]

If CPU power doubles how much will iecrease time for solving a problem? If the relationship between time and number of steps that the algorithm does be: T = 2^n i.e: A PC with 2GHz processor takes 4 ...
1
vote
0answers
52 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
78 views

What is the size of an algorithm? [on hold]

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, ...
-1
votes
0answers
40 views

Find number in Young tableau in $O(n+m)$

Give an $O(n+m)$-time algorithm to determine whether a given number is stored in a given $m\times n$ Young tableau. An $m\times n$ Young tableau is an $m\times n$ matrix such that the entries of each ...
-3
votes
2answers
78 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
votes
0answers
47 views

Will my solution work? Interview Question

So there is an interview question on interview cake. The question is given an array, how can you get the product of all the numbers except for the listed value. So let's say the array is [4,7,13,9]. ...
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
83 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
278 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
54 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
45 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
31 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
37 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
34 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
102 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
250 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
76 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
271 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
218 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
176 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
47 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
56 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
93 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
65 views

Analysing Space Complexity

I have to compute the space complexity of this function: ...
0
votes
2answers
43 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
72 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
63 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
92 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
31 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
93 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
20 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
36 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
76 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
26 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
27 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 ...
1
vote
2answers
86 views

Exercise on Divide&Conquer's technique

I need help on this exercise: You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all ...
3
votes
0answers
37 views

Alpha beta algorithm with Iterative Deepening analysis

I'm implementing a chess engine. Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster ...
1
vote
0answers
61 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
0
votes
1answer
106 views

How can I prove algorithm correctness? [closed]

How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the ...
4
votes
1answer
68 views

Period of a pseudo-random sequence generated using an LFSR

I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated ...
2
votes
3answers
104 views

Algorithm for finding all the combinations on a boolean array

I have to design an algorithm to do the next task: I have one array of booleans. For example: Array: [0 1 0 0 1 0 1 1] I want to obtain all the existing combinations of 1's, having in mind that ...
1
vote
2answers
152 views

Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
1
vote
1answer
97 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
1
vote
0answers
39 views

Why does the firefly algorithm need an intensity function?

I am studying the firefly algorithm and I would like to ask about the Intensity function that is defined at the beginning of the algorithm. What is it for? Some literature give different functions ...
1
vote
1answer
60 views

Amortized analysis of binary counter with increment and resetting operations

I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation. First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ because ...