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
1answer
11 views

DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Problem In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has ...
2
votes
1answer
26 views

Why does Bellman-Ford algorithm use < rather than ≤?

The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle? For instance, say I have the below example going ...
-1
votes
1answer
19 views
-1
votes
0answers
22 views
0
votes
0answers
18 views

Time complexity of simple function related to bits

I am wondering about correct answer to this task from a yesterday's test: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length ...
1
vote
1answer
21 views

Complexity analysis using big - O, Omega and Theta notation

I was reading a research paper and there I read the following: $t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\...
0
votes
1answer
19 views

how to prove correctness of this BFS algorithm?

Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that ...
0
votes
1answer
22 views

Recurrent relation for algorithms with two stages

I am trying to do the recurrence relation for my algorithm, but it has two variables $T(n,m)$. For sufficiently small $n$, $m$ is practically the same as $n$, but $m$ cannot grow beyond some constant $...
0
votes
0answers
30 views

Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
0
votes
0answers
15 views

Are these tradition algorithms analysis tools, such as Big O, still applicable to deep learning algorithms, such as AlexNet, VGG, GoogLeNet, ResNet?

Some deep learning algorithms are popular these days, such as AlexNet, VGG, GoogLeNet, ResNet. In computer science, big O notation is used to classify algorithms according to how their running time ...
0
votes
2answers
32 views

How to generate all combinations given an array of elements using backtracking?

Given an array, generate all combinations For example: Input: {1,2,3} Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} I am ...
1
vote
1answer
28 views

Weird implementation of quicksort

I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is ...
-3
votes
0answers
31 views

What is the space complexity of the following procedure? [duplicate]

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

What is the running time of the following procedure? [duplicate]

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
39 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 ...
2
votes
2answers
44 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
25 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
35 views

Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
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
716 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
577 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
50 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
21 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
63 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
31 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
29 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
26 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
48 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
33 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
31 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
62 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
50 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
45 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
42 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
56 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
19 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
104 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
66 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
38 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
51 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 ...