Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.

learn more… | top users | synonyms

3
votes
1answer
65 views

How many comparisons do we need to find min and max of n numbers?

Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers. Recurrence for the above problem ...
0
votes
1answer
26 views

How does these Probing time occurs for hash tables

I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is ...
0
votes
1answer
56 views

Dijkstra single-source shortest path $\Omega(n\log n)$?

If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case? I know heaps reduce ...
2
votes
2answers
69 views

How to go about proving an algorithm correct?

The algorithm (called as rmax(1,n)) finds the maximum of a list of numbers contained in an array S[1..n]. ...
2
votes
2answers
42 views

Counting inversion pairs - $n^2$ results in $n \log n$ time?

The number of possible inversions in an array is bounded by $\binom{n}{2}$, i.e $\frac{n(n-1)}{2} \in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(n\log n)$ time using something ...
4
votes
1answer
43 views

Why is the running time of edit distance with memoization $O(mn)$?

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with ...
2
votes
0answers
47 views

Choosing potential function in amortized analysis

How should I think to choose the potential function in the amortized analysis? More specifically are there techniques or tips for choosing optimal or good potential functions?
1
vote
0answers
37 views

Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
5
votes
2answers
137 views

algorithm time analysis “input size” vs “input elements”

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
4
votes
4answers
646 views

Is there a method for automatic runtime analysis of algorithms?

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms? I googled "Automatic algorithm analysis" which gave me this but it is too ...
0
votes
0answers
19 views

Nested Loop Complexity [duplicate]

I have several lists of varying size, each index of the list contains both a key and an object : list1.add('Key', obj). The lists are all sorted. My aim is to iterate through the list and match 1 or ...
3
votes
1answer
33 views

Asymptotic expected runtime of Randomized Algorithm

I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties: Given input size $n$, with probability $3/4$ it moves on to solve an ...
1
vote
1answer
42 views

Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys. Consider the ...
3
votes
1answer
23 views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
1
vote
0answers
36 views

Find the size of the maximum cycle in a MPS

Consider the following problem to be solved in a distributed context: Find for each processor the size of the biggest cycle of which it is member. My algorithm is the following (for synchronous ...
0
votes
1answer
25 views

Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?

In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of ...
3
votes
1answer
99 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

I was told this question may be better received here. Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind ...
2
votes
1answer
36 views

Big-O Notation of Anagram solution algorithm

In Solution 1: Checking Off of Problem Solving with Algorithms and Data Structures, just beneath the ActiveCode: 1 extract (included at the bottom of this post for reference), it is stated: each ...
5
votes
1answer
423 views

Would using the mean as pivot speed up quicksort?

Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only ...
2
votes
1answer
25 views

Amortize time for a counter with the operations INCREMENT and DECREMENT

Let a binary counter with the operations INCREMENT and DECREMENT. I need to show that you can't implement this kind of counter with constant amortized time per operation. Hence, I need to show ...
5
votes
1answer
46 views

Runtime of Euclidean Algorithm

Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of ...
0
votes
0answers
39 views

Runtime of “Look and Say” [duplicate]

I am trying to figure out what the time complexity is for a "Look and Say" sequence generator which receives an integer n and outputs the nth term in the look and say sequence. I'm looking at the ...
5
votes
1answer
152 views

Proof of Dijkstra Algorithm Optimality

Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing) I became curious when Wikipedia ...
2
votes
1answer
72 views

Algorithms online problems

I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations. As far as I can see, the sites that I ...
0
votes
1answer
113 views

Comparing random access and sequential access

Assume that we choose randomly $k$ distinct numbers $N_1$, $\dots$, $N_k$ in $\{1, \dots, k\}$ and we have a file of $k$ parts. We have these two cases : We read (or write) sequentially from part ...
1
vote
0answers
34 views

Is this Time analysis strategy right?

I'm working in the time analysis for an algorithm with two optional optimizations variant applied and followed next approach: Create inputs of different lengths for the algorithm Using these inputs ...
1
vote
0answers
24 views

Efficient flood filling (seed filling)

I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) ...
6
votes
2answers
58 views

Which measure of sortedness explains the phase transition in Quicksort's runtime?

I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is ...
0
votes
0answers
27 views

How many array access in keys[j] = keys[j-1]; vals[j] = vals[j-1];?

Are there two or four array accesses in the line keys[j] = keys[j-1]; vals[j] = vals[j-1]; I think it should be four. The reason I'm asking this is in ...
3
votes
1answer
87 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
0
votes
1answer
51 views

Time/Space cost of Taxicab algorithm?

The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type ...
0
votes
0answers
38 views

What is the average runtime of appending items to arrays?

It is the time of the year again in colleges for final exams and I am preparing mine as of now and I am finding myself in hot water when it comes to understanding the running times of appending items ...
1
vote
1answer
42 views

Loop invariant: decreasing a variable and swapping it

As an example exercise, we were asked to find the loop invariant for this bit of code. ...
2
votes
1answer
63 views

How can I make sense of amortized accounting method?

Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read). In the example of the Stack ...
2
votes
1answer
79 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...
2
votes
1answer
19 views

Big O notation and “input”

Suppose I have an algorithm that reads lines in a file(linear) and for each line in the file, it sorts each word(nlogn). This algorithm is mnlogn, where m is the number of lines and n is the number ...
1
vote
1answer
16 views

Average Case runtime for random choice search

Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime? My thoughts so far: The chance to find the ...
1
vote
2answers
32 views

Calculating the runtime for a recursive algorithm [duplicate]

If the runtime of a recursive algorithm could be expressed as $T(n) = \begin{cases}O(1) & n \leq c \\ k * T\left(\frac{n}{k}\right) + \left(k + n * k \right)\end{cases}$ what would be the ...
1
vote
1answer
79 views

Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., ...
2
votes
1answer
34 views

Proving approximation ratio

We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking ...
3
votes
1answer
48 views

Explanation of Summations for Algorithm Analysis

I do not have a background in Computer Science, work as a Software Engineer, and am attending college for my Master's degree in Computer Science. I have a data structures and algorithms course that I ...
1
vote
2answers
42 views

Proving the lower bound of compares in comparison based sorting

I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help ...
6
votes
1answer
739 views

What is the Big O of T(n)?

I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,. $$ I've established that $T(n) = \frac{1}{n}$ but now ...
0
votes
0answers
23 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
3
votes
1answer
40 views

Where would someone find amortized analysis more useful than average analysis and the opposite?

I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing ...
1
vote
1answer
73 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
8
votes
1answer
201 views

Solving recurrence relation with two recursive calls

I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very. In order to do this I ask myself the question ...
0
votes
1answer
49 views

Creating all possible subsets and complexity calculation [duplicate]

I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm. Now I would like ...
1
vote
1answer
52 views

Order of a pseudo code

I am trying to find order of an bellow algorithm but I have no idea about, the problem like below we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in ...
1
vote
1answer
73 views

What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?

Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of ...