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
-1
votes
0answers
13 views

What is the space complexity of the following procedure?

Please help me calculate the space complexity of the following program: int Sum(int A[ ], int n) { ...
0
votes
0answers
21 views

What is the running time of the following procedure?

Please help me calculate the time complexity of the following procedure. Power(n) 1:If n=0 then 2: return 1 3:else if 4: return Power(n-1) + Power(n-1) Explain ...
1
vote
2answers
28 views

Time complexity of finding predecessor for a dictionary implemented as a sorted array

I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it ...
1
vote
2answers
35 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
1
vote
1answer
23 views

What is the time complexity of a binary multiplication using Karatsuba Algorithm?

My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity. In general, the Karatsuba Multiplication is said to have a time complexity of ...
0
votes
0answers
32 views

Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
-1
votes
0answers
9 views

How would I find out how how to depict a certain set of numbers from a sum [closed]

I'm looking for an algorithm of sorts for my problem. I have 10 buttons, Alpha = 1, Bravo = 2, Charlie = 4, Delta = 8, Echo = 16, Fox = 32, Golf = 64, Hotel = 128, India = 256, Juliet = 512, Each ...
0
votes
0answers
16 views

Find the asymptotic time complexity of the following [duplicate]

while(n>1){ n = sqrt(n); } Where sqrt returns the root of n. n = 2^k and k is a power of 2.
9
votes
1answer
686 views

Why say that breadth-first search runs in time $O(|V|+|E|)$?

It's often stated (e.g., in Wikipedia) that the running time of breadth-first search (BFS) on a graph $G=(V,E)$ is $O(|V|+|E|)$. However, any connected graph has $|V|\leq |E|+1$ and, even in a non-...
4
votes
1answer
564 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
2
votes
1answer
44 views

How do I minimize the cost of some algorithm that performs some operation on a list?

I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
2
votes
0answers
33 views

When does knowing the number of solutions help (improve the running time)?

Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm ...
1
vote
1answer
20 views

How to get to the efficient solution of a problem on buying with exchange policy

I was working through some coding challenges at hackerrank.com and got to this one. I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. ...
0
votes
0answers
14 views

Calculating Time Complexity of Algorithm Using Incrementor Variable [duplicate]

I am trying to calculate the time complexity of an algorithm using n in the code below. I have a working solution to a coding challenge to sort a stack using only ...
0
votes
3answers
60 views

Is there a unit of measurement that can express code execution speed in absolute terms?

I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
0
votes
2answers
30 views

Karatsuba Multiplication Rule in dividing a Number in two parts

In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example: x= 1234 y= 2456 Then a = 12, b = 34, c = 24 , d = 56 What if ...
1
vote
1answer
28 views

Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...
1
vote
2answers
24 views

Run time for a specific loop confusion

I have a loop: for(int i = 1; i < N; i*=5) {...} where {...} is some statement. I'm trying to understand its run time. So, ...
1
vote
1answer
37 views

Worst Case Space Complexity of Merge Sort and Bubble Sort

I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(...
1
vote
1answer
32 views

Average Case Running Time of Quicksort Algorithm

From this website, it states that the average case of Quicksort algorithm is T(n) = T(n/9) + T(9n/10) + θ(n) Im a bit confused. Is it supposed to be ? ...
2
votes
2answers
28 views

Randomly built binary search trees

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove: The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$. We define "...
2
votes
2answers
57 views

A* without heuristic more efficient than Dijkstra

I am using the module networkx to operate on graphs made from OpenStreetMap. I wanted to compare the shortest path algorithm to ...
0
votes
2answers
49 views

Figuring out when one algorithm will be slower than another algorithm [closed]

I'm studying for a computing exam and came past the following question on a past paper and need help with it. When would algorithm A be slower than algorithm B? Demonstrate your answer with the help ...
0
votes
1answer
44 views

Question about how can i determine if counting sort is the right option over other sorting algorithms

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm. Now i find that solutions for that ...
0
votes
1answer
29 views

UCT (Upper Confidence bounds applied to Trees)

For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ? Besides, I do not quite understand how UCT deals with the flaw of ...
3
votes
3answers
55 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
0
votes
0answers
11 views

PSO codes that do not function correctly

I am new to PSO method. I wrote the codes following the standard approach. First initialise the position and velocity of each individual within the swarm, then set the target iterative rounds to ...
0
votes
1answer
37 views

Complexity of Double Selection Sort

I would like to find the best, average, worst-case complexities of below code. Its a variant of selection sort. In each pass both min and max is calculated and placed at proper position ...
2
votes
1answer
16 views

Analysis of straight insertion

I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot ...
6
votes
2answers
102 views

Is $\lceil\log n\rceil!$ polynomially bounded?

Considering the definition, $f(n) = O(n^k)$, for some constant $k$. If I choose $k = 100$ and plot, it shows $n^{100} > \lceil\log n\rceil!$ for all $n > 1$. However, the solutions to ...
1
vote
1answer
53 views

How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

Can someone tell me what am I doing wrong? Problem: https://codeforces.com/contest/22/problem/B Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) ) Eg: ...
0
votes
0answers
38 views

What is a uniform algorithm?

what is a uniform algorithm? I see some definitions based on running time, but also contradictory uses of slower uniform algorithms.
0
votes
0answers
39 views

$\Omega$-notation for insertion sort [duplicate]

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...
1
vote
0answers
32 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
0
votes
1answer
36 views

Finding the maximum disjoint weight in a weighted node graph

I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the ...
1
vote
0answers
37 views

Hypergraph sorting computational complexity

For a hypergraph, I want to know the computational complexity of this step in my algorithm what is the computational complexity of this kind of sorting Sort the hyperedges in descending order based ...
2
votes
0answers
38 views

Analysis quickselect: Median of Medians with duplicates

in This Lecture Notes 1 (page 3), it is said concerning quickselect with median of medians: If there are repeated elements ... Alternatively, one has to refine the algorithm and the analysis ...
2
votes
1answer
35 views

Conditions for maximum period of quadratic congruential method (PRNG)

$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$ Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"): $c$ ...
0
votes
0answers
9 views

Shortcuts/Patterns for being able to calculate the running time of a loop/algorithm? [duplicate]

This is my first question here. I, like many people, suffer from the lack of the ability to be able to determine the running time of algorithms just by looking at them. I've picked up on a few ...
0
votes
2answers
90 views

Why run -time of N-Queens using backtracking algorithm fluctuates?

I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$. I think the ...
3
votes
1answer
102 views

How to understand the recurrence relation and time-complexity of StoogeSort?

I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the ...
3
votes
2answers
123 views

Bubble Sort with “while” loop - why is average case n^2?

If Bubble Sort is written as: ...
2
votes
1answer
92 views

Subtree with minimum sum of nodes' costs

Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that ...
4
votes
1answer
41 views

How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
0
votes
1answer
26 views

Proof Big Theta (sum of a geometric)

Here sum of a geometric, where c is a positive real number. $g(n)=1+c+c^2+...+c^n$ $\theta(1)$ if $c<1$ Any idea to solve this?
0
votes
1answer
30 views

Big O of runtime operation n-m+1 [duplicate]

I have a loop that runs n-m+1 times where m = len(list_m) n = len(list_n) for i in range(n-m+1): Is this time complexity O(n-m+1)?
0
votes
0answers
17 views

Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
0
votes
1answer
35 views

Is it possible to compute how many iterations this algorithm will take?

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always ...
2
votes
2answers
399 views

All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$? All the examples that I could think of satisfy the above ...
1
vote
1answer
46 views

Time complexity of finding subsequences of a string segmented into parts

Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3. Then, we split $S$ into $N/3$ equal parts, each of length 3. For each equal part,...