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

2
votes
1answer
136 views

Big O Algorithm Analysis

I'm confused about the complexity of the following code: for(i=1; i<=n; i = 2*i) for(j=1; j<=i; j++) print A[j] I know that the first loop is ...
0
votes
0answers
12 views

Optimizing the output parameters for a given input

Problem statement: I'm trying to solve a problem statement using C# as programming language. In the problem system for an input (double/decimal) say Hi, the output generated is a form of dataset ...
0
votes
0answers
15 views

Parallel program - strange benchmark results [on hold]

so I've written a parallel program and benchmarked it on my stationary computer, a server computer, my laptop. The benchmark results on my laptop are quite confusing. On the server and my stationary ...
1
vote
1answer
22 views

Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case [duplicate]

I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most ...
4
votes
2answers
61 views

Compare Complexity of Graph Algorithm

Assume I know that there is an algorithm of complexity $ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $ for a Graph $G(E,V)$. How do I compare this for example to the complexity of $ ...
6
votes
2answers
557 views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
-1
votes
2answers
35 views

merge sort merge phase

I'm watching a video, demonstrating merge sort, https://www.youtube.com/watch?v=EeQ8pwjQxTM At 5:42, happens something I do not understand. We are merging last 2 big arrays, ...
1
vote
0answers
28 views

Deterministic Selection Median of Medians [duplicate]

As I understand, a quick-select algorithm could use median of medians to find best suited pivot to yield the i-th item in the array, say A. I have referred to Median of Medians algorithm and steps ...
0
votes
0answers
18 views

How to calculate order of growth for the given loop? [duplicate]

int sum = 0; for (int i = 0; i < N; i++) for (int j = 1; j <= N*N; j = j*2) sum++; According to me the outer for loop will run O(N), and the ...
1
vote
1answer
68 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
0
votes
1answer
32 views

Reb-black tree amortized cost of the rebalancing

I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions). How can it be proved?
1
vote
1answer
31 views

Regex to NFA to complement

So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear. Now to go from that NFA to the complement of the NFA, since I can't just flip accept ...
0
votes
0answers
17 views

How to show the running time of the following algorithm? [duplicate]

The outer loop runs $n$ times. The inner loop runs $\lfloor \frac{n}{i} \rfloor$ times. So it would be $O(n \cdot \lfloor \frac{n}{i} \rfloor)$. I do not know how to transform that into a proper ...
0
votes
0answers
56 views

Analyzing a sorting algorithm [duplicate]

Each of n distinct values is equally likely to be put into pile 1 or in pile 2, independent of each other. These piles are then sorted from smallest to largest. The two sorted piles are then merged ...
0
votes
1answer
39 views

Differentiating between BubbleSort and InsertionSort

This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this. The problem is this: You have two unknown sorting algorithms, one is Bubble Sort, the ...
-1
votes
0answers
12 views

Prove that double bubble sort is a Big-Theta(n^2) algorithm [duplicate]

Double bubble sort=every other run through the elements bubbles the smallest element down to the front of the list. How do I prove that it is theta n^2? Edit: other runs bubble largest elements up ...
-1
votes
1answer
64 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
0
votes
2answers
43 views
6
votes
1answer
109 views

What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037. This is my proposed solution to compute the $n$th value: ...
2
votes
2answers
61 views

Recurrence relations when function call is made inside loop

int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n – k); return x; } What is the value of fun(5)? I ...
3
votes
1answer
20 views

Why use minhash instead of directly computing Jaccard coefficient?

Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute. ...
4
votes
0answers
31 views

What's the time complexity of Monte Carlo Tree Search?

I'm trying to find the time complexity of Monte Carlo Tree Search (MCTS). Googling doesn't help, so I'm trying to see how far I get calculating it myself. It does four steps for ...
2
votes
0answers
17 views

What would be the time complexity if a recursive function is inside a loop? [duplicate]

I am confused in calculating the time complexity for a recursive function inside a loop. ...
10
votes
2answers
227 views

Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
0
votes
1answer
31 views

Reccurrence equation and finding suitable algorithm

I'm given the following recurrence equation: $$\begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && ...
2
votes
0answers
90 views

Why do we focus on asymptotics when analyzing algorithms? [duplicate]

Maybe a newbie question, but why when we analyze algorithms do we focus on asymptotics? It seems to me the performance of algorithms on finite input sizes (after all, problems are rarely infinitely ...
1
vote
0answers
55 views

Space Complexity

This particular code is written in C. ...
1
vote
1answer
53 views

How Splitting Summation method works

I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and ...
38
votes
3answers
6k views

Not sure if there is a mistake in a computer science book or if I am misunderstanding something

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
2
votes
2answers
90 views

What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k. Usually one traverses the "express line" (i.e. the top lane ...
4
votes
1answer
29 views

How can I calculate optimal batch sizes for calls to an external server?

So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - ...
1
vote
2answers
88 views

How many recursive calls does it take to compute binomial probability weights?

I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen ...
4
votes
3answers
59 views

Scientifically acceptable method for comparing performance of algorithms

I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the ...
4
votes
1answer
97 views

Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?

I was reading CLRS and it mentions that if $p$ is a prime of the form $4k+3$ and $a$ is a quadratic residue, then $a^{k+1}$ is a square root of $a$. One can also easily show that $a^{-k}$ is a square ...
7
votes
1answer
175 views

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates ...
1
vote
1answer
25 views

Run-time analysis of distributed network decomposition algorithm

I'm trying to understand the run-time analysis in the article [1]. The authors define the following notation: $g(n) = \hat O(f(n))$ if $g(n) = O(f(n)^{O(1)})$. In the run-time analysis of their ...
3
votes
1answer
33 views

Average Case Complexity Rivisted

I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem: Suppose we have a 5 elements array to be sorted using ...
7
votes
2answers
123 views

Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square ...
4
votes
1answer
28 views

How does one find a non-quadratic residue modulo $p$?

I was wondering how one can find a non-quadratic residue modulo $p$ and what the runtime of this algorithm would be. I thought that one can use the Legendre Symbol $$ \left( \frac{a}{p} \right) = ...
3
votes
1answer
49 views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...
1
vote
1answer
72 views

Is O(ln n) “exponentially faster” than O(n)?

I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear ...
4
votes
1answer
25 views

What is the average-case complexity of trial division?

The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, ...
0
votes
0answers
22 views

Huffman Coding vs LZW Algorithm

I'm trying to understand comparisons between the two. Is there ever a case where is it better to use Huffman Coding over LZW? Could the compression ratio for Huffman ever surpass that of LZW? ...
3
votes
1answer
49 views

Why is the path compression (no rank) for disjoint sets $O(logn)$ amortized for Find-Set?

I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set. I was told that the potential function: $$ ...
0
votes
0answers
15 views

Time complexity with flooring of nested function calls [duplicate]

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
2
votes
1answer
37 views

Upper bound of algorithm with flooring

Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm. $$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$ $$T(1) = 0$$ Solution is given as: $$T(n) = ...
1
vote
1answer
18 views

Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$. ...
0
votes
0answers
45 views

Isomorphic induced subgraph problem using Courcelle's theorem

The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$. Is there a proof using ...
2
votes
2answers
44 views

Branchless function equivalent

Does every pure function have a branchless equivalent? By pure function I understand a function that uses only its input values and no global state to produce the output. By branchless function I ...
-1
votes
1answer
22 views

Question regarding the potential method for amortized analysis [closed]

What does the following mean exactly for the potential method? Is this applicable to all situations? If the potential is positive, then we overcharged for some operations. If it is negative, we ...