Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
2
votes
0answers
20 views
Why does Shellsort work well on Sorted and Reverse ordered lists?
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.
...
1
vote
1answer
38 views
Finding the lower bounds of an algorithm
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.
For eg, I have the following algorithm
...
1
vote
2answers
72 views
Why don't we scale the cost of memory access when analyzing runtime of algorithms?
Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
1
vote
1answer
30 views
Resolving this recurrence equation [duplicate]
I have this recurrence equation:
$T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$
$T(1) = 1$
I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
1
vote
1answer
29 views
Approximate time for selection operation using index when equality is on nonkey
In database query processing, the approximate time for selection operation using primary index when equality is on key is $2(b_s + b_t)$ where $b_s$ is disk seek time and $b_t$ is disk transfer time ...
3
votes
2answers
65 views
Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is
$\qquad ...
1
vote
1answer
69 views
What is a computer year?
In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?
4
votes
1answer
34 views
Parallel merge sort using hypercube connection template
I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.
What I ...
0
votes
0answers
39 views
Complexities of basic operations of searching and sorting algorithms
Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is ...
2
votes
1answer
36 views
Decreasing runs of inner loop in outer loop [duplicate]
I am trying to determine the worst case runtime of this program:
while n > 1
for i = 1,..,n
m = log(n)
n = n/2
Obviously the outer loop runs ...
2
votes
1answer
114 views
How to get expected running time of hash table? [duplicate]
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
-2
votes
1answer
87 views
Complexity of slightly tricky for loop
I'm trying to determine the complexity of this for loop:
for (int j =3; j <= n-2; j+=2) {
....
}
By trying out lots of examples, I came up with ...
-3
votes
1answer
79 views
Complexity of a while loop that divides by parameter by three each iteration
I've learned that a while loop such as
int i = 100;
while (i >= 1){
...
///Stuff
i = i/2
}
will run in logarithmic time, specifically, ...
1
vote
2answers
57 views
Common Algorithms without Asymptotically Tight Bounds
I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
4
votes
1answer
72 views
How to get the expected running time of an algorithm
I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise.
It uses a direct access ...
2
votes
0answers
46 views
Leftist heap - determining time complexity
The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the ...
2
votes
4answers
152 views
Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?
I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).
Why does ...
3
votes
1answer
131 views
Worst case analysis of bucket sort using insertion sort for the buckets
Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode).
In the worst case, this would ...
2
votes
2answers
111 views
Analyzing programs with multiple for-loops
If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these...
the ones like
...
1
vote
2answers
95 views
Finding the complexity of a recursive method
An assignment question asks me to find the complexity of a [tail] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is ...
1
vote
1answer
97 views
What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?
Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to ...
3
votes
3answers
76 views
5
votes
1answer
142 views
Potential function binary heap extract max O(1)
I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method.
I ...
7
votes
2answers
145 views
Simplify complexity of n multichoose k
Edit: In my case, $k$ may be greater than $n$ and they grow independently.
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was ...
1
vote
1answer
70 views
Computing the clustering coefficient
I saw in this video that computing clustering coefficient of central node of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct?
...
0
votes
1answer
86 views
A question about parallel algorithm complexity
When in a Parallel algorithm we say:
"This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with ...
2
votes
1answer
227 views
Question about Prims algorithm where weights are between 1 and some constant W
I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of ...
1
vote
1answer
191 views
Triple nested for-loops [duplicate]
Possible Duplicate:
A puzzle related to nested loops
I am trying to count the exact/total number of iterations the following nested for-loops are executed:
...
2
votes
1answer
76 views
Input to make worst case on big O not possible?
Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a ...
0
votes
2answers
153 views
What is the time complexity of the following program?
Please help me calculate the time complexity of the following program.
int fun (int n) {
if (n <= 2)
return 1;
else
return fun(sqrt(n)) + n;
}
...
1
vote
2answers
552 views
How can I prove that a build max heap's amortized cost is $O(n)$?
Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?
1
vote
1answer
168 views
Iterative binary search analysis
I'm a little bit confused about the analysis of binary search.
In almost every paper, the writer assumes that the array size $n$ is always $2^k$.
Well I truly understand that the time complexity ...
1
vote
0answers
90 views
Is it possible to analyse computation?
Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation.
So you have a ...
0
votes
1answer
295 views
Base of logarithm in runtime of Prim's and Kruskal's algorithms
For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot ...
1
vote
2answers
221 views
Runtime analysis of a nested loop
I have some difficulties performing the worst case analysis on this algorithm.
The outermost loop is executed $2N$ times.
The while loop, in the worst case, will increase by $2$ each time, so it ...
5
votes
1answer
953 views
A d-ary heap problem from CLRS
I got confused while solving the following problem (questions 1–3).
Question
A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 ...
2
votes
2answers
130 views
How to go about working the average case run time of this trivial algorithm (and other algorithms)?
This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here.
...
0
votes
1answer
109 views
Complexity of optimized bubblesort
What is the runtime complexity of the following implementation of Bubblesort (for integers)?
...
4
votes
1answer
641 views
Best-Case Running Time For Binary Search Tree Insertion
The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:
The term best-case performance is used in computer science to ...
8
votes
1answer
260 views
Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?
The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS.
...
3
votes
1answer
55 views
2
votes
1answer
89 views
Doubt with a problem of grown functions and recursion tree
I'm confused to conclude the recursion tree method a guess for the next recurrence:
$$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$
I write some costs for the levels of tree, you ...
1
vote
3answers
525 views
Big O: Nested For Loop With Dependence
I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
6
votes
3answers
259 views
Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?
If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get ...
2
votes
0answers
349 views
Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs
This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
8
votes
3answers
220 views
Why use comparisons instead of runtime for comparing two algorithms?
I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
5
votes
0answers
172 views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
1
vote
2answers
839 views
Time complexity formula of nested loops
I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.
...
3
votes
0answers
243 views
Analysis of a linear-time algorithm for longest palindromic substring
Background
$\newcommand\ldotd{\mathinner{..}}$Last month, I heard about a new linear-time algorithm to determine the longest palindromic substring called Jeuring's algorithm. It seemed interesting, ...
4
votes
2answers
239 views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
