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
1
vote
1answer
21 views

Demonstrating that probability for every possible result is uniform at the end of an algorithm

I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$. At ...
1
vote
2answers
32 views

What is the time complexity of this “reverse words” algorithm?

I had to write an algorithm that, given the input ['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's'] would return ...
1
vote
1answer
49 views

Kirchhoff's Spanning Tree Algorithm

Recently I have studied Kirchhoff's spanning tree algorithm to count the number of spanning trees of a graph, which has the following steps: Build an adjacency matrix Replace the diagonal entries ...
2
votes
1answer
82 views

How to compare n number of m-dimensional points among one another with minimum time complexity?

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
1
vote
0answers
32 views

Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real). Can we use this machine to sort an array in $O(n)$? I don'...
0
votes
0answers
28 views

Proof: Quick Sort Is $O(n*logn)$

I was given the follow proof: $$T(n)=n+2T(\frac{n}{2})$$ Will prove that $$T(n)=O(n*logn)$$ For $2:$ $$T(2)=2+2T(1)=2\leq 2*log(2)$$ Assume it is correct for $n-1$ in particular for $\frac{n}{2}$ ...
0
votes
0answers
13 views

How to detect self loop in graph using greedy algorithm if given list of number of degrees

if you are given list of n integers that represents the degree of a graph. How to detect if there self loop in the graph using greedy algorithm.
3
votes
1answer
56 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. I´ve made a program to check this statement and it ...
0
votes
1answer
129 views

Why is my algorithm version so slow with this input?

Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (...
0
votes
0answers
14 views

Learning algorithm analysis

Im learning order of algorithm For x>=2, and rand(x) is function that return 1 value from 1 to x-1 which have uniform probability $\frac{1}{x-1 }$ And max(x,y) output bigger value and min(x,y) output ...
0
votes
0answers
49 views

Algorithm Analysis - Binary Search Algorithm

The problem is from Data Structures and Algorithm Analysis Edition 3.2 (Java Version) Book from Clifford A. Shaffer. It is from the third chapter exercises, problem number 3.13.20. Below is how it is ...
0
votes
1answer
22 views

Partitioning a set based on binary predicate

Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which ...
1
vote
1answer
23 views

Dijikstra's algorithm with “hull” value catch

Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here. Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...
1
vote
2answers
258 views

Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
9
votes
2answers
177 views

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
0
votes
0answers
9 views

learning the private key by reusing same random variable k in ELgamal

i wonder: if for some reason, someone, say alice, sends unencrypted messages to bob and signs it using elgamal signature, can oscar,the adversary, gain knowledge of the private key if alice reused the ...
1
vote
0answers
19 views

Dynamic programming for subsequence metric

Let $a = a_1, \ldots, a_n, b = b_1, \ldots, b_m$ be sequences of positive integers and for any respective subsequence of length $k$, we consider $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2$. Given a bound $...
1
vote
2answers
37 views

Converting IPV4 address into Binary

So given an IP address it is converted into binary via calculating the binary of all different segments and then joining them. For example, 12.32.18.01 converted into a binary it would amount to this ...
1
vote
0answers
11 views

When was the dynamic array first introduced as an example for amortized analysis?

I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
0
votes
1answer
39 views

How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list

How to divide an unsorted list into two equal parts in linear time, where every element in the first part is smaller than every element in the second part I tried to use QuickSort but in can result ...
1
vote
1answer
40 views

Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

I am having difficulties in understanding why the recurrence $$T(n)=3T(n/4) + n\log n$$ is solvable with Master Method but $$T(n)=2T(n/2) + n\log n$$ isn't? Despite they both look very similar ...
1
vote
0answers
29 views

Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
-1
votes
1answer
31 views

What does the search problem imply about the decision problem?

Let $\Pi_{dec}$ be an NP-complete decision problem and let $\Pi_{opt}$ be its corresponding optimization problem. Assume $\Pi_{opt}$ can be solved in polynomial time. What does this imply for $\Pi_{...
0
votes
0answers
8 views

Study of cache behaviour of algorithms on Virtualbox

I want to study certain cache oblivious algorithms and cache behaviour of some other algorithms I wrote in general. I want to understand, is it advisable, if I do this study in an virtualized ...
0
votes
1answer
33 views

What is the time complexity in solving a polynomial equation of degree N in one variable?

How easy/difficult(in terms of big-O) is it to solve polynomial equations of high degrees of N? Do apps like Desmos actually solve equations to get roots or do they approximate roots by iterating ...
1
vote
0answers
24 views

Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
0
votes
1answer
31 views

Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
0
votes
1answer
39 views

In Big-O notation, what does it mean for T(n) to be upper bounded by something

I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? ...
1
vote
0answers
11 views

equivalent sub-keys in DES encryption

i am trying to understand the DES cryptosystem and was wondering: what would've happened if all of the sub-keys were equal? does it reduce the security? can we actually find the keys if we know all ...
1
vote
0answers
60 views

How to prove that an algorithm has no deadlock

I need to mathematically prove that this algorithm is deadlock-free: ...
0
votes
1answer
27 views

Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard?

Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete? This would be where the goal is to group a multiset whose size is evenly ...
0
votes
2answers
34 views

Can algorithms of arbitrarily worse complexity be systematically created?

We’ve all seen this: Can we get worse? Part 1: Can mathematical operations of increasing orders of growth be generated, with or without Knuth’s up-arrow notation? Part 2: If they can, can ...
0
votes
1answer
74 views

How to prove NP-completeness of this variant of the set cover problem?

The problem exactly: Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least ...
0
votes
1answer
21 views

degree distribution

Does anyone know how to compute node degree distribution in a graph ? I am talking about a large graph for example California road network and imagine we have some data such as number of nodes and ...
1
vote
0answers
23 views

Intersection of 2 arrays

Here is a question i came across : Given two arrays, write a function to compute their intersection.Here we will allow the duplicates. Note: Each element in the result should appear as many ...
0
votes
0answers
32 views

Number of multiplications and additions in the given code

$N:=2^p$ Input: $f \in \mathbb C^N$ 1: $n=N/2$ 2: initialize vectors $f^{(1)}, f^{(2)} \in \mathbb C^n$ 3: $w_N^0=1$ 4: for $j=0,\ldots,n-1$ do 5: $\ \ \ \ \ f_j^{(1)}=f_j+f_{j+n}$ 6: $\ \ \ \ ...
0
votes
1answer
53 views

Time Complexity of the below code? [duplicate]

here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part. What is the time complexity ...
0
votes
2answers
67 views

Does DFS in an unweighted DAG find the shortest path for each vertex from a source?

I have many questions which related to this topic. I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths of all vertex by ...
1
vote
1answer
43 views

Worst Case running time of the Minimum Vertex Cover Approximation algorithm

Considering this factor $2$ minimum vertex cover approximation algorithm : Repeat while there is an edge: Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. ...
1
vote
3answers
61 views

How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity. I tried to derive it on paper. Let T(n) =...
2
votes
1answer
42 views

An algorithm for topological sorting based on depth-first search: why do we need two tags?

Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows: ...
1
vote
1answer
38 views

What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]

What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ ...
1
vote
0answers
29 views

Understanding the behaviour of different variations of Binary Search

Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of ...
0
votes
1answer
25 views

Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))

I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds. I ...
2
votes
2answers
138 views

Multiple choice knapsack dynamic programming

Giving a the following: A list of a store items $T=\{t_1, t_2,...,t_n\}$. A list of prices of each item $P=\{p_1, p_2,...,p_n\}$. A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
0
votes
0answers
45 views

time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
1
vote
0answers
18 views

Traceless In-place Selection

I was asked a question in an exam You are given an array A[1..n] of length n with each cell containing a ⟨height,weight⟩ pair. All height values are distinct, and so are all weight values. The array ...
1
vote
0answers
127 views

Data structure for storing strings

I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) ...
1
vote
2answers
151 views

How can I make my algorithm more efficient or Is there a better way to solve the problem

Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you ...