Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.

learn more… | top users | synonyms

-1
votes
0answers
21 views

Expected number of comparisons of Randomized Quick Sort [on hold]

Consider the Randomized Quicksort algorithm that where a pivot is chosen at random using a random generator. Suppose that we execute this algorithm on input array [5, 11, 7, 8]. In the following ...
2
votes
0answers
11 views

Residence time in multi server system

I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is: ...
0
votes
0answers
16 views

Confusion with space and time usage [duplicate]

The following is my own set-up code: ...
1
vote
2answers
34 views

Cost of shifting a number

I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001. I was thinking that the time complexity is $\Theta(n)$, ...
-1
votes
0answers
22 views

Amortized analysis : Dynamic arrays

While reading lecture notes on amortized analysis, I came upon the example of dynamic arrays, where you expand the array when it is completely full and shrink it when it is $\frac{1}{4}$ full. The ...
0
votes
0answers
20 views

Runtime and space usage of a snippet of code [duplicate]

I've been trying to understand time complexity and space complexity by writing my own snippets of code and solving them. Can you see if I'm correct? ...
0
votes
0answers
27 views

Asymptotic analysis of shifting/multiplying

I am currently working on the asymptotic analysis of Karatsuba algorithm and I have this line "return (X * B^ (2 * m)) + ((Z) * B ^ (m)) + (Y)" where X,Z,Y are ...
3
votes
2answers
84 views

Why does quicksort work well with virtual memory?

Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is ...
0
votes
1answer
25 views

Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values

How can I prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values ? It seems obvious to me, since an ill-conditioned problem is that ...
1
vote
1answer
16 views

Big-O Time Complexity of nested for loops [duplicate]

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3): ...
2
votes
1answer
36 views

Kosaraju's algorithm's time complexity

I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that using an adjacency list representation gives a time complexity of ...
1
vote
1answer
23 views

Efficient computation of Kronecker product

Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such: $M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty ...
1
vote
1answer
37 views

Expected number of random interval flips needed for sorting a random array

This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort. Assume that $A$ is an array initialized by a random ...
0
votes
2answers
67 views

Is there a way to find path length to a node from root in a binary tree?

I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in ...
-2
votes
1answer
37 views

Finding the time complexity of fibonacci sequence [on hold]

I tried it as follows and would like to know if it is correct.
0
votes
1answer
49 views

Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
4
votes
1answer
58 views

Parallel algorithms on a fixed number of processors

Usual parallel algorithms require a number of processors that grow with the size of the input, usually $O(\log n)$ or $O(n)$. This is great from a theoric point of view, but strange from a practical ...
-3
votes
0answers
40 views

is there an algorithm to calculate the sum of two egyptian fractions? [closed]

I would like to create a programm of egyptian fractions and the sum and substraction of them
0
votes
0answers
29 views

Improve the runtime of hashtable operations by keeping lists in sorted order

The following is a question from the textbook Introduction to Algorithms, however a solution to the problem is not given... Professor Marley hypothesizes that he can obtain substantial performance ...
0
votes
0answers
12 views

Regarding number of iterations in Value Iteration

In value iteration for single goal problem, does the number of iterations it takes for the convergence to terminate dependent on grid world size, or discount factor or threshold set or none of the ...
0
votes
0answers
20 views

Count comparisons in insertion sort that uses binary search to find correct postion

Assume a list $L$ is to be sorted using the following variation of insertion sort: For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position. ...
0
votes
2answers
56 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
-3
votes
0answers
23 views

Question about big-O notation (specific example) [duplicate]

i have a question about big-O notation. I Really appreciate if anyone help me out, because this is driving me crazy!! here is the Algorithm : ...
6
votes
1answer
55 views

Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
1
vote
2answers
59 views

How to find the Branch factor of 8 Puzzle

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that: Suppose,for example we wish to establish the ...
-1
votes
0answers
35 views

How to calculate the time complexity of the following function [duplicate]

The time complexity of the following code is O(2^n), could you please explain to me why? int f(int n) { if (n == 1) return 1; return 1 + f(f(n-1)); } Thanks ...
23
votes
7answers
6k views

Is it a problem to be a programmer with no knowledge about computational complexity?

I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess. Then I made ...
0
votes
0answers
13 views

Creating an algorithm with a certain worse case runtime [duplicate]

The inputs are x sorted lists (in increasing order) and in each list there are j/x elements (we are assured the numbers will work out to be a natural number. eg: j = 9, x = 3 L1 = [1, 2, 5], L2 = ...
0
votes
1answer
40 views

Average Time Complexity of Searching An Array [closed]

Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must ...
1
vote
0answers
35 views

Given an algorithm, what are the probabilities for its run-time cases?

I am given this algorithm And I am also given the fact that $1 \leq k \leq n$. If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
1
vote
1answer
34 views

How to write recurrence relation for the following scenario?

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 min{no. of leaf-nodes in ...
0
votes
1answer
24 views

Big O notation comparison with constant time [duplicate]

So, I'm new to this whole asymptomatic notation with respect to algorithms. So say you have a $f(n) = 1/n$ and $g(n) = 1$, would it be OK to say that $f(n)$ is not equal or is not an element of ...
1
vote
1answer
44 views

Gale–Shapley algorithm is man-optimal

I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page ...
3
votes
1answer
210 views

Algorithm analysis in the presence of undefined functions

I wonder how we can perform algorithm analysis when in an algorithm we have calls of functions whose definition we do not know, e.g. functions delivered by external libraries.
-1
votes
0answers
16 views

Shouldn't the outer sigma run from 0 to N-2 for selection sort runtime?

This is code from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf slide 6 ...
0
votes
1answer
62 views

What is “potential speedup” in parallel computing?

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy I wonder how "potential speedup" ...
3
votes
1answer
69 views

Why is the complexity of this nested for loop not $O(n^2)$?

I have the following pseudo-code: mystery(n): if n <= 50 : for i = 1 ... n : for j = 1 ... n : print i*j else : mystery(n-1) For ...
1
vote
1answer
22 views

How to compute time complexity of a program if the time complexity of a function called inside a loop is known? [duplicate]

This is the question- Let $A[1,....,n]$ ba an array storing a bit $(1\,\,or\,\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program - ...
1
vote
1answer
65 views

Find one-variable recursive formula for running time of Karatsuba multiplication

I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion ...
0
votes
0answers
52 views

Why is removing the second largest element from a max-heap not in O(log n)?

I have a max PriorityQueue designed using a heap. A function removemax() that removes and returns the element with the largest priority in $\Theta(\log n)$ and a function insert in $\Theta(\log n)$ ...
1
vote
3answers
95 views

How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. ) The professor, ...
0
votes
0answers
10 views

Variations of Master Theorem for Divide and Conquer [duplicate]

Are there any variations of the Master Theorem for Divide and Conquer other than that which is provided in the book "Introduction To Algorithms" by Cormen,Leiserson,Rivest,Stein?
0
votes
1answer
56 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
0
votes
3answers
51 views

Can the runtime of functions with no loops change with the number of calls?

How can we perform time complexity analysis on a function that has no loops? int somefunction(int param) { if (something) do this; else do this; } ...
2
votes
1answer
42 views

Precise runtime of the algorithm to find number of digits in an integer

Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm ...
1
vote
2answers
285 views

Why does randomized Quicksort have O(n log n) worst-case runtime cost?

Randomized Quick Sort is an extension of Quick Sort in which pivot element is chosen randomly. What can be the worst case time complexity of this algo. According to me it should be $O(n^2)$. Worst ...
1
vote
1answer
23 views

Subset-sum approximation algorithm running time

in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$ Essential part of this algorithm is trimming. On every step you delete all numbers which close ...
3
votes
1answer
57 views

Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
0
votes
2answers
68 views

Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

Why is it the lower the h(n) cost the more nodes need to be expanded in A*? As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html If h(n) is always lower than (or ...
1
vote
2answers
135 views

More efficient DFS on trees

Lets say for simplicity sakes I have a simple balanced binary tree of height h and I am doing Depth First Search. I generally do the following skeletons: ...