Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
1
vote
1answer
117 views

Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?

$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$ The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{...
1
vote
1answer
68 views

Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$? How can the function on the left be compared to a whole set?...
0
votes
0answers
274 views

Count Unique Subsequences to Destination?

I am looking at this post: Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , ...
0
votes
0answers
32 views

Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
0
votes
0answers
102 views

Intuition behind the entire (amortized) concept of Fibonacci Heap operations

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The potential function for the Fibonacci Heaps $H$ is defined as follows: $$\Phi(H)...
2
votes
1answer
77 views

$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al. In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
2
votes
0answers
48 views

Complexity of approximating a function value using queries

I am looking for information on problems of the following kind. There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
3
votes
1answer
69 views

What is considered an asymptotic improvement for graph algorithms?

Lets say we are trying to solve some algorithmic problem $A$ that is dependent on input of size $n$. We say algorithm $B$ that runs in time $T(n)$, is asymptotically better than algorithm $C$ which ...
0
votes
1answer
38 views

Complexity analysis of m!/n!(m-n)!

Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else? Please elaborate. Thanks
8
votes
7answers
4k views

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$. def is_equal(a: int, b: int) -> bool: return a == b <...
5
votes
3answers
2k views

What is the expected time complexity of checking equality of two arbitrary strings?

The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters. So far so good. I think we can all agree that ...
0
votes
1answer
135 views

Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order ...
0
votes
1answer
20 views

Do we have to calculate time for declaring statement in RAM model?

Do we have to calculate time for declaring statement, in my case int num3 statement. The following question was asked by professor as a post-lecture quiz. I ...
0
votes
0answers
24 views

In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$

Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
2
votes
0answers
43 views

trouble solving the recurrence 4T(n/2) + n

I am having trouble figuring out how to solve this recurrence problem... $$ \begin{aligned} &4T(n/2) + n \\ = &4(4T(n/4) + n/4) + n \\ = &16T(n/4) + 2n \\ = &4^kT(n/2^k) + kn \end{...
1
vote
1answer
39 views

For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that ...
1
vote
1answer
29 views

Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ ...
1
vote
1answer
16 views

Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?

I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification. Now as far as I have learned that that while the ...
1
vote
0answers
67 views

Clarification of the analysis of the worst case situation of quicksort as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. and I came across their analysis of the worst case of the quicksort algorithm. I could not quite understand a few specific ...
2
votes
1answer
47 views

Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure. The procedure is as follows: <...
0
votes
1answer
55 views

Proving building a balanced BST out of sorted array is $\Theta(n)$

I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$ I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$ I tried to prove it by induction but got stuck ...
0
votes
1answer
25 views

Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$?

Given an input $S$ (set of elements) find an exact three cover for a list of 3-element sets named $C$. $S$ = 1,2,3,4,5,6 $C$ = [1,2,3],[4,5,6],[3,1,2] Algorithm 1.Sort list and delete occurrences of ...
0
votes
1answer
60 views

Calculate the number of iterations in unusual nested loop

I am trying to calculate the number of iterations of a sequence of nested loops of the form: \begin{equation} N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1 \end{equation} ...
1
vote
1answer
70 views

Running Time Analysis of a Simple Binary Search Algorithm

I'm stuck with the following problem by Skiena (The Algorithm Design Manual, p. 106): Problem: Give an efficient algorithm to determine whether two sets (of size $m$ and $n$, respectively) are ...
2
votes
3answers
74 views

Little O notation relationship

Given the functions $𝑓(𝑛)=𝑛^{n}$ and $𝑔(𝑛)=10^{10n}$, I am trying to establish the following relationship: $𝑓(𝑛)\notin o(𝑔(𝑛))$. I know to show for the opposite, $𝑓(𝑛)\in o(𝑔(𝑛))$, I ...
0
votes
1answer
37 views

Time complexity analysis of 2 arbitrary algorithms - prove or disprove

We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size. We denote the worst time complexity of each ...
2
votes
1answer
99 views

What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$?

I was solving the following problem, just for reference (441 - Lotto). It basically requires the generation all $k$-combinations of $n$ items ...
0
votes
1answer
112 views

Algorithm Analysis of Three nested loop

I'm trying to figure out Time function and Big O of a nested loop code, ...
1
vote
1answer
73 views

Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort

This same question has been asked here so many times by several people. This is a problem which was asked in an entrance exam. And I am having difficulties in digesting the correct answer of this ...
0
votes
1answer
46 views

Minimum Subsequence Sum Algorithm Verification

I have an algorithm which is meant to solve the following computational problem: Input: Sequence of positive integers Output: A Sub-sequence of some desired length derived from original Sequence such ...
0
votes
0answers
24 views

What is the runtime of this pseudocode?

I need help figuring out the runtime of the following pseudocode. I believe it is O(|E| + |V|), but I'm not totally sure... ...
0
votes
1answer
47 views

Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer?

I had trouble formatting the summation symbols, so if anyone knows how to do it correctly feel free to edit. I just read the asymptomatic analysis chapter from CLRS. While the aggregation and ...
0
votes
1answer
20 views

How to represent a recurrence that increments by one at each tree level?

I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ I ...
2
votes
2answers
172 views

How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

I am aware that to get a running time by recursion tree method, we need to draw a tree and find: a) number of levels in tree. Since left side of tree decreases by 1 in size, so it's longest path ...
0
votes
1answer
228 views

Solving the recurrence of recursive insertion sort

I have solved that the recurrence of running time of the algorithm given as $$ T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases} $$ So the ...
1
vote
2answers
55 views

Algorithms: Determining Asymptotic Notation from a given execution time

I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it. Question 1: An Algorithm with ...
1
vote
1answer
143 views

Worst-case expected running time for Randomized Permutation Algorithm

I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a ...
1
vote
0answers
68 views

Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?

When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure. Using Fibonacci-heaps instead, are we not able to achieve a ...
1
vote
1answer
244 views

Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
2
votes
2answers
54 views

Does the word “efficient” usually refer to polynomial time or polylogarithmic time?

This question is strictly about terminology. I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
1
vote
1answer
30 views

Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?

This is probably a very basic question but one that I am having trouble finding a definitive answer for since this kind of thing is skimmed over in most introductory algorithms courses. Take an ...
1
vote
0answers
53 views

How to find the asymptotic bit cost

I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and ...
2
votes
0answers
80 views

How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?

Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm: Create a set S of remaining possibilities (...
0
votes
0answers
32 views

Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
0
votes
2answers
97 views

Need help analyzing the runtime analysis of this algorithm/algorithms in general

This is the algorithm I was trying to find the runtime of (doSomething) - ...
-1
votes
1answer
178 views

Asymptotic Analysis of Nested Loops with Conditionals

I'm trying to run an analysis of a set of nested loops so that I can determine the value of variable sum after the outer loop is finished. The code is as follows: <...
1
vote
0answers
87 views

Time Complexity of a Naive Solution to Merge K Sorted Arrays

There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following naive solution: ...
0
votes
2answers
52 views

Algorithm Running Time

I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such: If a $\Theta(\log_2{n})...
2
votes
2answers
999 views

Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
2
votes
1answer
34 views

Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...

1
2
3 4 5
…
19