Questions tagged [algorithm-analysis]

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
35 views

Maximizing total value of coins collected

Suppose we have $m$ bags of coins. There are $n$ possible denominations of coins, i.e a coin can be of value $v_1,...,v_n$. Now each bag contains some coins and also two different bags may contain ...
  • 11
0 votes
0 answers
24 views

Bit model vs RAM model confusion

I've been struggling with this analysis of algorithms notion for a few hours now in an introductory course. Let us define a function $N(n)$ for positive integer $n$ as the number of times performing $...
0 votes
0 answers
22 views

Karger’s Min Cut algorithm: Cut after contraction is cut in original graph

Assume that Karger’s Min Cut algorithm is used on a graph $G=G_0=(V, E)$. Then, for $i>0$ let $G_i$ be the graph after the $i$th iteration of the Min Cut algorithm which is obtained by contracting ...
0 votes
1 answer
28 views

Geometric Set Cover in one dimension

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem. The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
  • 11
2 votes
2 answers
42 views

Describing the set of Running Time of all Turing Machines

Consider the set of all valid Turing Machines descriptions $T_{All}$, and the set of functions that denote the real (not asymptotic) running time of Turing Machines in $T_{All}$, lets call it $R_{All}$...
  • 23
-4 votes
1 answer
42 views

Protein folding, P vs. NP, and DeepMind with AlphaFold

"DeepMind has predicted the structure of almost every protein so far catalogued by science, cracking one of the grand challenges of biology in just 18 months thanks to an artificial intelligence ...
  • 3
4 votes
2 answers
954 views

Does T(n) = 2 · T(2n) + n apply to Master method?

I'm trying to apply the master method to the following recurrence: $$T(n) = 2 \cdot T(2n)+n.$$ We have $a=2$ and $b=1/2$. Also, $f(n)=n$ and $n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$ since $\log_{1/2}...
  • 99
1 vote
1 answer
51 views

Big O analysis of a sorting algorithm that counts smaller elements

How do I prove the runtime of an algorithm with Big O notation? I don't know much about O notation, I just I know how to compare sets of functions with each other and I'm also familiar with the master ...
  • 13
0 votes
0 answers
23 views

Prove that Fibonacci code for data compression is a complete code using Kraft-McMillan inequality

I am Facing a problem when learning about data compression. I learned that the Fibonacci code for data compression is complete. I am trying to prove it using a hint from my professor to use Kraft-...
0 votes
0 answers
30 views

In two level perfect hashing from CLRS we use m = n at the first level for expected space<=3n. Instead if we choose m = αn can space be decreased

In two level perfect hashing scheme shown in CLRS 3rd edition 11.5, this also has a great explanation here We set m = n at the first level and then for secondary hash tables we set mi = n^2. This ...
0 votes
1 answer
18 views

Algorithm to find best order for items on pages with a fixed height

I am looking for an algorithm to find the best order of items to fit on pages. Consider the following case, we have a page with the height = 300 We have images with the following heights - [150,200,...
1 vote
1 answer
33 views

Is it possible to measure how fast the humans are moving their bodies with different level(slow, normal, fast) from video?

Examples like swinging both of their hands squat walking around jump around etc Is it possible to perform this in real time under crowded scene without depth information? I can find out the "...
1 vote
0 answers
51 views

Runtime of this algorithm

I have an algorithm with running time that satisfies $$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
  • 247
0 votes
0 answers
262 views

MergeSort's merge function loop invariant

I am reading a proof of correctness for the MergeSort Algorithm. This is the code for the MergeSort and the Merge function: The correctness of the MergeSort function is easy to prove since the two <...
  • 108
0 votes
1 answer
81 views

search for the next prime number more efficiently?

...
  • 13
0 votes
1 answer
81 views

How to calculate error bounds for the function behind the following algorithm?

D.E. Knuth, in his infamous The Art of Computer Programming, section 1.2.2, presents the following algorithm to efficiently calculate logarithms based on the method used by Henry Briggs: Suppose that ...
0 votes
0 answers
63 views

What is the expected time complexity of this algorithm?

In the following algorithm $A[1..n]$ denotes an array $A$ of size $n$, of $n$ distinct integers. Func1() and Func2() are functions that run in $\mathcal O(\log n)$ and $\mathcal O(n)$ time, ...
  • 247
0 votes
1 answer
34 views

Understanding why this upper bound is tight

Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree ...
  • 247
-1 votes
1 answer
36 views

Inequality about External path length

First of all LPL is Leaf path length & IPL is internal path length. While i was studying algorithm analysis for average complexity of binary search , i saw that inequality. Before that, i proved ...
  • 3
0 votes
1 answer
49 views

Checking if a graph contains a (not necessarily simple) cycle of length more than k

I'm struggling with question 7-38 from Skiena's Algorithm Design Manual: Let G be a directed graph. We say that G is k-cyclic if every (not necessarily simple) cycle in G contains at most k distinct ...
  • 103
0 votes
0 answers
63 views

Analysis of randomized algorithms

The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$ which leads to the ...
  • 247
1 vote
0 answers
63 views

Is it true that: $f\notin o(g)$ implies $\exists c>0: f > cg$ infinitely often

My (attempt at a) proof is as follows: $f\in o(g)$ means that $\forall c>0 \exists n_0 \forall n\geq n_0: f(n) \leq cg(n)$. Now taking the complement we get: $\exists c>0 \forall n_0 \exists n\...
  • 11
1 vote
1 answer
97 views

Expected runtime of recursive algorithm with optional part

I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
1 vote
2 answers
128 views

How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?

Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure ...
0 votes
0 answers
61 views

Derive the formula (n-m+1) number of comparisons for worst case Brute-force string matching algorithm

I am trying to understand how (n-m+1) (n being the string and m being the pattern) is ...
  • 13
1 vote
7 answers
186 views

How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?

I know that Quicksort or MergeSort are faster than, say, Bubblesort or Selection sort. And I know why (complexity metrics) but I never been able to find out how could someone start with, for example ...
  • 113
0 votes
2 answers
193 views

Combining fork() and algorithms

Today in my algorithms class, my professor explained how in divide and conquer algorithms we do things in "parallel" although I felt it was not exactly in parallel. Then I remembered from OS ...
0 votes
0 answers
41 views

Can 0 be a tight upper bound of -4n?

I'm newbie in algorithm time complexity. I had a function, f(n) = 2n2 - 4n. I have to proof that f(n) = O(n2). We can take it ...
1 vote
2 answers
64 views

Average runtime random search without replacement

Consider an algorithm that is tasked with searching the array A. Let n be the size of the array, let i be a random number between 1 and n. Finally, k is the target object we are searching for. If A[i] ...
1 vote
0 answers
40 views

Understanding how the total # of comparisons is derived for the worst case in the "Brute-Force String Matching" algorithm

The Total number of comparisons for the worst case in the "Brute-Force String Matching" algorithm is: (n-m+1) where ...
  • 13
-4 votes
1 answer
36 views

Prove or give a counterexample of o(f) = O(f) − Θ(f)

Prove or give a counterexample: for every function f from non-negative integers to non-negative reals, o(f) = O(f) − Θ(f). Here “−” denotes the set minus operation. I try to make some tryout but ...
1 vote
2 answers
56 views

Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays

Consider an array A[1..n] that first increases up to some point p then it decreases until some point q and then increases again. That is A[k] < A[k + 1] for all k in [1..p] and [q..n] and A[k] >...
0 votes
2 answers
69 views

Recurence Relation, specifically understanding substitution rule used

This is a pretty vague question and can be applied to many math problems not just recurrence relations. Above I fully understand, setting up the recurrence relation from the algorithm given. And how ...
  • 13
2 votes
1 answer
51 views

Constructing a small set of numbers whose differences cover $\{1,\ldots,n\}$

Let $n\in\mathbb N$. Given a set $S\subset\mathbb N$, let $\Delta(S) = \{a-b\mid a,b\in S\}$ denote its set of differences. I'm interested in finding a small set $S_n$ such that $\{1,\ldots,n\}\...
  • 141
-1 votes
2 answers
188 views

What is the time complexity of the following program

The right answer is Theta(n log logn). But, can someone explain why it is the case? I know intuitively that it is because k is k^2 each time, so it couldn't be (logn) for the second loop. However, ...
0 votes
0 answers
27 views

How to apply Hyperloglog to count distinct elements but with condition

I'm going to adapt the Hyperloglog algorithm to count distinct numbers from a stream. But now, it is more challenging; say, there is a condition: the number needs to exist in the database so that it ...
  • 1
0 votes
0 answers
31 views

Substituting back into a recurrence relation

This may be super simple, but there is something I can not stop thinking about while doing the "plug and chug" algorithmic analysis on F(n){ if(n = 0){ return 1 } else{ return f(n-1)n } Now ...
-3 votes
2 answers
45 views

Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$

Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.
  • 1
0 votes
0 answers
31 views

How to calculate how many times a function inside a for loop inside a while loop will be called?

I'm studying for my exams and a came through this exercise but I can't prove the result I found. Given this piece of code: ...
1 vote
1 answer
110 views

What is the optimal algorithm for merging an arbitrary number of convex hulls?

Preparata & Shamos in "Convex Hulls: Basic Algorithms" (1985), give a linear algorithm for merging two convex hulls in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices in ...
-2 votes
1 answer
35 views

Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
0 votes
0 answers
27 views

Persona matching algorithm

I have a project to match two groups of people. Under insurance, if the initial sales agent leaves the insurer, their customers will become so-called “orphan customers”. I've given a big data set ...
  • 1
0 votes
0 answers
20 views

Give examples of data structure usage which can be used and cannot be used in amortized analysis

Preparing for my finals in my "advance algorithms" course. In one of the previous exams, there was the following question: Let there be some arbitrary data structure (it is not known ...
  • 231
0 votes
2 answers
38 views

Loops running time as function of n

Suppose I have the following code and I'd like to compute running time as function of $\ n$: ...
  • 157
1 vote
1 answer
50 views

Relation between algorithms and models

I have found this question some time ago. While reading it, I had a problem with understanding the following idea: Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...
1 vote
1 answer
225 views

time complexity to convert string to integer and vice a versa

just given solution on this post i had mention the time complexity to convert string to int is O(n), also verifying this post now in one of comment fellow SO user, corrected me with example also ...
1 vote
0 answers
36 views

The complexity of Steinberg's strip-packing algorithm

In reading the paper "a strip-packing algorithm with absolute performance bound 2", the author gives a recursion formula $T(l)=T(l')+T(l'')+O(min\{l'\log{l'},l''\log{l'}',l\})$, where $l'+l''...
1 vote
1 answer
42 views

Contradicting asymptotic analysis in recurrence equation?

I'm trying to solve the recurrence equation from CLRS ed 2. $$ T(n) = 2T(\sqrt{n}) + 1 $$ The question says the solution should be asymptotically tight, but at first I didn't read it and solved it ...
1 vote
0 answers
35 views

Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
2 votes
1 answer
82 views

Lower bound for ϵ-tester with one-sided error for the "2-injective" property of functions

An $\epsilon$-tester given an input and a property, is defined as follows: If the input holds the property then the tester should accept with probability at least $\frac 2 3$. Otherwise if the input ...
  • 123

1
2 3 4 5
39