Tagged Questions

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

learn more… | top users | synonyms

1
vote
1answer
16 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 ...
3
votes
1answer
36 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
34 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 ...
4
votes
1answer
124 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 ...
1
vote
1answer
65 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 ...
1
vote
0answers
38 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
32 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
21 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
51 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
26 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
81 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
35 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
35 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
37 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
45 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
75 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 ...
-1
votes
0answers
21 views

Runtime of assembler program [duplicate]

I want to analyze the asymptotic runtime of a RAM program under the uniform and the logarithmic cost. To find the asymptotic runtime under the uniform cost do I just have to count the instructions?? ...
2
votes
1answer
16 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
15 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
30 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
65 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
30 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
45 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 ...
0
votes
1answer
20 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
736 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
36 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
68 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
195 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
38 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
51 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 ...
2
votes
1answer
49 views

How do we analyze Algorithms with parallelism features

As I am comparing between two algorithms, I was wondering which is the best approach to use to compare between the both. Big-O seems not the perfect metric for me, as the it's based on the worst-case, ...
0
votes
0answers
17 views

Cache lines to store an $s \times s$ matrix

I am reading Frigo's "Cache Oblivious Algorithms" paper. On page3 near the bottom, it says: An $s \times s$ submatrix is stored on $\Theta (s + s^2 / \mathcal{B})$ cache lines. Why is this so? ...
1
vote
0answers
53 views

Prove the correctness of Tarjan's off-line least-common-ancestors algorithm

Tarjan's off-line least-common-ancestors algorithm is given as follows: LCA($u$) Make-Set($u$) Find-Set($u$).$ancestor$ = $u$ for each child $v$ of $u$ in $T$ $\quad$ LCA($v$) ...
4
votes
3answers
55 views

Is there a technique for statically checking that a function is only called at a particular rate?

I was reading this article about types, and started wondering how static type checkers could enforce other properties in programs. For example, say I wanted to create a language which would allow ...
0
votes
0answers
15 views

Big o notation for the algo [duplicate]

Asked this at programmers Stack Exchange, was recommend to ask here : What would be the big o for the algo: for (i=0; i < n*n; i++) for(j=0; j<i*i; j++) ...
2
votes
0answers
37 views

Frigo's cache-oblivious algorithms paper

I am reading Frigo's "Cache-Oblivious Algorithms" paper and I need help understanding his cache complexity expressions for the base cases. He starts on page 3 with "An $s \times s$ submatrix is ...
0
votes
1answer
75 views

Time Complexity for matrix multiplication? [duplicate]

How can I find out the time complexity for the brute-force implementation of matrix multiplication for: Two square matrices ($n \times n$), Two rectangular matrices ($m \times n$) and ($n \times ...
2
votes
0answers
34 views

Constant in Complexity of SQRT algorithm

this is my first question in CS so I apologize if this question is off-topic. If we use Newton`s Method for finding square root then complexity is $O(M(n))$ (using Wikipedia Notation: $M(n)$ is the ...
2
votes
1answer
57 views

What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a ...
0
votes
0answers
29 views
-2
votes
1answer
47 views

Asking for help with this Therac 25 bugged code. I don't understand the explanation

Therac 25 is a radiation therapy machine that lead to 3 deaths and 3 injuries in 1980s. That's the worst accidents in history which are caused by software bugs. In 1993, Leveson and Turner did a ...
0
votes
1answer
102 views

What is the runtime of the following code? [duplicate]

Can you explain to me how you get the Big O notation for the runtime of the following snippet of code? ...
1
vote
0answers
57 views

Influence of edge number and priority-queue implementation on the runtime of Dijkstra

When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
0
votes
0answers
73 views

stuck on proving the optimality of a greedy algorithm [closed]

I'm Ph.D. student doing research in wireless networks. My past projects are more oriented to systems than theory. For my current project, I devised a greedy algorithm for an optimization problem. ...
1
vote
0answers
59 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
0
votes
1answer
39 views

Maximum value a variable can hold without documentation [closed]

Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data ...
6
votes
1answer
64 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
0
votes
1answer
30 views

Understanding when to count key comparisons

I understand that for something like Linear search, this would be the key comparison: if(itemToFind == a[i]) return i; If I put this method into another ...