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
-2
votes
0answers
18 views

Java error Exception in thread “main” java.util.NoSuchElementException [closed]

The code below has the error: Exception in thread "main" java.util.NoSuchElementException. Does anyone can give me the idea how to fix? import java.io.*; import java.util.Scanner; class ...
0
votes
0answers
22 views

How to know that the substrings 01 and 10 does not require an infinite amount of memory to count the substrings [duplicate]

Why does {w | w has equal number of 01 and 10 substrings} not require an infinite amount of memory to “count” the number of 01 and 10 substrings?
0
votes
0answers
37 views

Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...
1
vote
0answers
27 views

Is there a branch of CS about studying function calls branching?

I know little about computer science. I wrote a function that has some ifs and may call itself recursively. Is there a branch of computer science that studies these possible branches? I'd like to ...
0
votes
1answer
28 views

A visitor at a political convention with n delegates

So I have been asked to specifically construct a divide and conquer algorithm for the question: "You are a visitor at a political convention with n delegates; each delegate is a ...
1
vote
1answer
36 views

How would I prove that the regular expression rejects string?

Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$. Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused ...
1
vote
1answer
22 views

Number of Comparisons in an Algorithm

The number of comparisons in the following algorithm is supposed to be $3n/2 - 3/2$ if $S$ is odd. I understand that the for loop is $3n/2$ comparisons, but I fail to see where the $-3/2$ comes from. <...
1
vote
1answer
22 views

Finding a tight bound for a recurrence relation

Problem: Give tight asymptotic bounds $( \Theta )$ for the following function: $$ T(n) = T(n-2) + n $$ Answer: We are not given the base case. I am going to assume that $T(0) = 0$ and $T(1) = 1$. Here ...
-1
votes
2answers
35 views

Finding a lower bound for the expression $\log(n!)$

Problem: Is $\log(n!) \in$ $\Omega( n^n )$? Answer: Since $n! > n^n$ for all $n > 1$ we can conclude that: $\log(n!) \in$ $O( n^n )$. Let us look at the special case where $n = 4$. \begin{align*}...
0
votes
2answers
42 views

Finding a lower bound for the expression $\ln^k(n)$

Problem: Assume that $k \geq 1$ and $\epsilon \geq 0$, is $\ln^k(n) \in$ $\Omega( n^\epsilon)$? Answer: In the special case of $\epsilon = 0$, I claim the answer is no. I suspect the person who wrote ...
-1
votes
1answer
13 views

Given the following state diagram, write out its formal definition as a 5-tuple

I got these for four of them, but I can't get the transition function. Q = {q1, q2, q3, q4} Σ = {a,b} q1 is the start state, and F = {q4}
1
vote
0answers
65 views

Prove that if given an integral flow, an acyclic integral flow exists with the same value

We are given a directed network $G=(V,E)$ with capacity $c(e)$ on edge $e\in E$, and a feasible $s$-$t$ flow $f:E\rightarrow \mathbb R^+$. A flow $f$ is acyclic if the subgraph of directed edges with ...
1
vote
1answer
41 views

Finite automata start state

Can a finite automata not have a start state? I think it is possible for a finite automata to not have a start state. However, I'm not sure if I'm correct.
0
votes
0answers
19 views

Recurrence relation of an algorithm

how can I know what are the recursive calls of this algorithm ? in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation. Here is the algorithm :
1
vote
1answer
65 views

Find minimum number of points which intersect overlapping arcs

Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time. I'm having some trouble proving ...
2
votes
1answer
116 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
1
vote
1answer
25 views

How to use Runge–Kutta methods in a second order ODE

Consider a second order equation $F=ma=m\ddot{x}$. In the language of Euler's method $\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$ $\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$ $x(t+dt)=x(t)+\dot x(t)dt$ Basically, ...
1
vote
1answer
33 views

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$ My approach with recurrence tree: $n \sim n\log(n)$ $\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$ $\frac{n}{4} \...
1
vote
1answer
31 views

Average case analysis by key comparisons of Max Sort

I'm having trouble approaching this average case analysis in terms of key comparisons. The pseudo-code is as follows: ...
3
votes
0answers
45 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
1
vote
0answers
73 views

Can somebody please explain what are these variables doing here?

I have this algorithm: I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum ...
0
votes
0answers
19 views

Computer Science [duplicate]

I am trying to solve the following problem to find big-theta. I am having a lot of trouble, if anyone can help! T(n)=8T(√n)+log^2(e^n)? The logarithm is base 2 and is squared.
8
votes
3answers
89 views

How can we find the number of pairs of intersecting ranges on a circular number line?

I recently thought of and managed to solve this algorithmic problem: On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers <...
0
votes
0answers
33 views

substitution method - proving karatsuba algorithm is not O(n)

I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence: $$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\ 3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
1
vote
1answer
37 views

Can someone help me fully grasp idea and time/space complexity with this code?

My understanding is the following: Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
0
votes
0answers
43 views

Counting number of sequences summing to target

This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading: We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
0
votes
1answer
60 views

For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink?

I am stumped on the following question: For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also ...
2
votes
0answers
44 views

Experts problem with one perfect expert

This question concerns a variant of the 'experts' problem and the randomized weighted majority algorithm that can be used to solve it. This is the description of the problem from Wikipedia: Imagine ...
1
vote
1answer
44 views

Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$

I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my ...
1
vote
2answers
46 views

Asymptotic bounds of the following operations

I have a very simple question about the best possible big-O bounds for the following data structure: It starts out empty When you add an element, it is inserted, and the index it was at is associated ...
1
vote
2answers
61 views

Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?

In my analysis of algorithms class we were given the following recurrence relation: \begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
1
vote
1answer
20 views

How to analysis the complexity of this LIS program?

I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site. Given a fixed curr, the for-loop in ...
0
votes
0answers
53 views

Need help with a very specific Greedy Algorithm. Are there fast solutions?

i need help for a specific problem i have at work. You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000: Row 1 might look ...
1
vote
0answers
18 views

Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges? [duplicate]

I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first ...
1
vote
1answer
37 views

Maximum integer in a sorted list which also is in an unsorted list

If I have a sorted list $A=[a_1, \dots, a_n]$ such that the integers $a_1\leq a_2\leq\dots\leq a_n$, and an unsorted list $B=[b_1, \dots, b_k]$, which includes at least one integer also in $A$, can I ...
-2
votes
1answer
33 views

recurrence relation for this n queen problem algorithm . and the time complexity

I am not able to understand how to write a recurrence relation for this n queen problem algorithm down below. Recurrence relation is for n*n board and the time complexity ...
4
votes
1answer
57 views

Las Vegas algorithm for finding 00000 in bit string

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
1
vote
1answer
47 views

Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?

The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation. The author then argues that this is ...
3
votes
0answers
38 views

Hardness of an instance of a problem independent of algorithms?

The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
0
votes
1answer
18 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
0
votes
0answers
14 views
1
vote
1answer
37 views

Master theorem: $T(n)=10T(n/9)+n\lg(n)$

I am told to solve the recurrence $$T(n)=10T(n/9)+n\lg(n)$$ using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $...
0
votes
0answers
24 views

Analysing the complexity of a recurrent function i+1,j*2

Let's say we start with $i = 1$, $j = 1$, $i \leq n$, and $j \leq i$ and then increment $i = i+1$ and $j = 2j$, respectively. The output prints $k$ times, which represents the inner loop. Output: <...
0
votes
0answers
14 views

Finding upper bound on number of I/Os needed to generate all permutations of some input in external memory

The general approach outlined in this paper in its proof of the lower bound on the average number of I/Os needed to obtain a given permutation of some input in external memory is as follows. Note that ...
1
vote
0answers
36 views

Fibonacci Heap that consolidates after every step

The lecturer of my graduate algorithms course suggested that, even if a Fibonacci Heap would consolidate its tree list after every operation (not just when doing deleteMin()), most operations would ...
1
vote
1answer
31 views

What is a “negative function” withing algorithms?

I am currently studying the book 3rd edition CLRS Algorithms textbook, Chapter 3. I had the exact same question as this post but I have one more question now: What is a negative function? These ...
1
vote
1answer
39 views

Loop invariance insertion sort algorithm

I have the following pseudo code for a insertion sort algorithm ...
1
vote
1answer
22 views

Algorithm for evaluating polynomials

I'm reading The Algorithm Design Manual and I stumbled upon this problem. I can't really get my head around this, I don't even know how the number of multiplications could differ, what I mean is that ...
1
vote
2answers
42 views

How to analyse the time complexity of an algorithm based on the input values in addition to input size

I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input value in ...
-2
votes
1answer
48 views

Condition in the Dependent Loops

I'm stuck with nested for loops that are dependent on the previous loop: for (i=1; i<=n; i++) for (j=1; j<=i; j++) x = x+1 the part that is confusing ...

1
2 3 4 5
36