# 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.

1,943 questions
Filter by
Sorted by
Tagged with
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
24 views

• 99
1 vote
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
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-...
• 121
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 ...
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
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
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
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
81 views

...
• 13
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 ...
• 13
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
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
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 ...
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
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
63 views

• 141
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, ...
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 ...
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 ...
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.
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
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 ...
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 ...
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
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
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
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
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 ...
• 111
1 vote