Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
49 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
2
votes
0answers
39 views

Update each element to product of all others in linear time, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. I have only been able to find an $O(nlog(n))$ time and $O(log(n))$ ...
1
vote
0answers
35 views

A look at an exact smallest grammar algorithm. How do we compute running time big-O?

A smallest grammar of a string $s$ over an alphabet $\Sigma$ is a smallest CFG $G$ such that $L(G) = \{s\}$, where size is the total number of symbols occuring on the right sides of production rules ...
1
vote
1answer
27 views

Proof of the master thorem case with floors and b = 2

This question is related to my previous one. Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$ and $f(n) = \Theta(n^{\log_ba})$. Then $T(n)...
1
vote
0answers
27 views

How much of the x86 instruction set does blender use? [closed]

I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
1
vote
1answer
30 views

Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ ...
0
votes
0answers
16 views

Realtime pairing algorithm [closed]

I am building a Game with online playing feature. In database, maintaining user details along with his level. I am using redis database to store the online userids as keys and busy/free as value. ...
1
vote
1answer
32 views

Polynomial time algorithm - Matching pairs of vertices

Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
1
vote
1answer
43 views

Proving correctness of inefficient algorithm - Path between two vertices

Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity ...
1
vote
1answer
15 views

why is the max number of Nodes mod(N/m) + mod(N/m^2) + 1 in R-tree?

I am going through Antonin Guttman's paper on R-tree. It mentions the max no of nodes given N index records in an R-tree is |N/m| + |N/m^2| + 1. If there are N ...
2
votes
3answers
331 views

Why aren't primality tests easily linear in time complexity?

Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear. I assume it's not linear only if we compare the ...
2
votes
3answers
52 views

How to properly calculate dependent nested loops for big-O [duplicate]

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, ...
2
votes
2answers
47 views

Finding the k-th smallest ternary sum of elements from three different arrays

The problem goes like this: Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+...
1
vote
0answers
34 views

Array subset division with equal sums

Today I stumbled upon a problem which looked like the partition problem but certainly is different. Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
1
vote
1answer
12 views

Terminology for reducing runtime of an algorithm by using a property of the problem?

It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property. For example, $P$ could be the problem of searching ...
2
votes
1answer
29 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
0
votes
1answer
27 views

What will be big O complexity for this loop? [duplicate]

I am not able to understand time complexity of this for loop. While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity? ...
0
votes
0answers
22 views

Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
-1
votes
0answers
36 views

How to find the maximum difference between n numbers efficiently?

Suppose there are n employees and I need to find the difference between maximum and minimum salaries of these n people. What would be the most efficient way to do that? Will $O(n)$ time work?
1
vote
1answer
68 views

Dijkstra’s shortest path algorithm

I'm learning about single source shortest path algorithms and need to clarify few doubts- Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers. Does ...
-2
votes
1answer
18 views

Few questions about Mergesort and Recirsion algorithms

Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted. How to use recursive algorithm to find the least element of a finite list of unsorted numbers ...
0
votes
1answer
34 views

Big O analysis for problem where number of items searched is unknown

Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in ...
0
votes
0answers
15 views

Merge Sort Recurrence analysis for list of strings [duplicate]

I saw this question and tried to find out what the time complexity was: Using the recurrence relation for Merge Sort: $$T(n)\; =\; merge\_time\; +\; 2T(n/2)$$ Here, since we have a list of strings, ...
0
votes
1answer
21 views

Big O analysis trying to follow a logic

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? I am trying to follow the logic of the solution provide while myself have a different approach. Here is my ...
1
vote
1answer
13 views

Approximation factor shorthand clarification

I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation ...
1
vote
0answers
21 views

Determining a value in an algorithm on its first run

I was given the following algorithm as a solution to one of my problems. However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never ...
4
votes
0answers
49 views

Distribution of pointer keys in a Skip-list node

Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$. We construct a skip list over the keys. Now if I pick a key (e.g. 31 in the ...
0
votes
1answer
23 views

n-DNF boolean formula k satisfiability

Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n). Where input is infinite number of n tuples where ...
-2
votes
1answer
33 views

Counterexample to an Algorithm Complexity Statement

Say I have the following statement: If $f(n) = O(s(n))$ and $g(n) = O(r(n))$, then $f(n) - g(n) = \Theta(s(n) - r(n))$. What would be a counterexample to this?
0
votes
1answer
19 views

Time complexity dependent on magnitude of input [duplicate]

I'm trying to analyze an algorithm that looks like this: def foo(L): for n in L: for x in range(n): ... What would be its time complexity?...
0
votes
2answers
57 views

Big O notation for finding duplicates in a list using binary search

I've written an algorithm to find duplicate integers in a sequential list of integers, but I'm running into issues when trying to calculate it's worst case complexity. Given a sequential list of ...
1
vote
1answer
23 views

Find the efficiency class

I have to find the efficiency class of this algorithm b = 3 a = 4 for i = 4 to n^2 if (i mod 2 == 0) a = a+2 else b = b*3 end for I ...
1
vote
1answer
20 views

Find total number of assignment in the worst case?

I have this algorithm Algorithm (A[1..n]) for i <- 1 to n do if (A[i] < 0) then A[i] <- 1 * A[i] End if End for I ...
2
votes
1answer
28 views

Is there a way to theoretically compare hash functions?

Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions ...
-1
votes
2answers
69 views

Why do you need at least ln(n!) many comparison to sort a list?

"If every element comparison (testing whether $a_i \le a_j$ ) provides at most one bit of information, argue that you need at least on the order of $\ln(n!)$ many tests/comparisons to sort the list." ...
0
votes
1answer
109 views

What is the difference between “algorithm,” “process” and “program”?

I am currently studying algorithms and algorithmic design, and I am confused those terms. What is the difference between them? Thank you.
0
votes
1answer
55 views

Big-O notation for nested loops that might skip iterations

When you have an algorithm that may skip a lot of iterations due to a hash table lookup, do you still count the iterations that are exited immediately? Hypothetical example: ...
0
votes
0answers
14 views

time complexity of recursive algorithm with loop [duplicate]

For approximating a recursive algorithms time complexity i found some great techniques e.g. here. But i'm not sure how one to get the time complexity of a recursive algorithm with a loop in it. For ...
1
vote
1answer
55 views

Big O space complexity of this isAnagram method

I'm currently debating with some friends what is the Big O space complexity of this isAnagram method: ...
-1
votes
1answer
51 views

Finding time complexity when while loop included [duplicate]

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, ...
0
votes
2answers
44 views

When to add and when to multiply to find time complexity [duplicate]

I am trying to learn how to determine time complexity. Sometimes, I see complexity as $\log n + \log n = 2\log n$ but sometimes I see complexity as $\log n\cdot\log n$ which is $(\log n)^2$. Suppose ...
1
vote
1answer
131 views

Given max-flow determine if edge is in a min-cut

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
0
votes
1answer
105 views

Complexity of finding a majority element

I was given a question that is stated that; Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection ...
0
votes
1answer
36 views

Determining an appropriate number of buckets for a hash function

I would like to select an appropriate number of buckets in my hash table for this scenario: A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed ...
2
votes
0answers
22 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
2
votes
1answer
33 views

minimum number of nodes that traverse all the graph

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
2
votes
1answer
26 views
0
votes
1answer
79 views

Calculate the average length of the linked lists in a hash table

I am learning hash tables, and I would like to know how to determine the average length of the linked lists. For example: A hash table holds about 10,000 employee records. Each record is indexed by ...
0
votes
0answers
32 views

If you have two recursive calls in a function and one terminates before the second how do you calculate the time complexity? [duplicate]

Suppose you have a function which calls to itself twice. So both go down recusively until they reach some condition. But one of them will go less times than the other. For example one would call ...