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

learn more… | top users | synonyms

6
votes
2answers
547 views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
1
vote
0answers
28 views

Deterministic Selection Median of Medians [duplicate]

As I understand, a quick-select algorithm could use median of medians to find best suited pivot to yield the i-th item in the array, say A. I have referred to Median of Medians algorithm and steps ...
1
vote
1answer
68 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
1
vote
2answers
67 views
+100

Identifying system events affecting timing behavior of an application

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job? My question is purely in the context of Worst Case ...
0
votes
0answers
17 views

How to show the running time of the following algorithm? [duplicate]

The outer loop runs $n$ times. The inner loop runs $\lfloor \frac{n}{i} \rfloor$ times. So it would be $O(n \cdot \lfloor \frac{n}{i} \rfloor)$. I do not know how to transform that into a proper ...
0
votes
0answers
56 views

Analyzing a sorting algorithm [duplicate]

Each of n distinct values is equally likely to be put into pile 1 or in pile 2, independent of each other. These piles are then sorted from smallest to largest. The two sorted piles are then merged ...
0
votes
1answer
39 views

Differentiating between BubbleSort and InsertionSort

This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this. The problem is this: You have two unknown sorting algorithms, one is Bubble Sort, the ...
-1
votes
0answers
12 views

Prove that double bubble sort is a Big-Theta(n^2) algorithm [duplicate]

Double bubble sort=every other run through the elements bubbles the smallest element down to the front of the list. How do I prove that it is theta n^2? Edit: other runs bubble largest elements up ...
-1
votes
1answer
64 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
1
vote
1answer
79 views

Does Heapsort work in time o(n log n) in the best case?

Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs? For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about ...
-2
votes
0answers
51 views

Runtime of function 5…5^N nested loops [duplicate]

How do I compute the runtime of this? Is it 5^1 + 5^2 ... 5^n? p:= 1 s := 0 for i=1 to n do p := p * 5 for j=1 to p do s := s + 1
6
votes
1answer
109 views

What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037. This is my proposed solution to compute the $n$th value: ...
1
vote
3answers
144 views

String Comparison vs. Hashing

I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed: Comparing two ...
3
votes
1answer
20 views

Why use minhash instead of directly computing Jaccard coefficient?

Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute. ...
2
votes
0answers
17 views

What would be the time complexity if a recursive function is inside a loop? [duplicate]

I am confused in calculating the time complexity for a recursive function inside a loop. ...
1
vote
0answers
55 views

Space Complexity

This particular code is written in C. ...
1
vote
2answers
88 views

How many recursive calls does it take to compute binomial probability weights?

I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen ...
1
vote
1answer
24 views

Run-time analysis of distributed network decomposition algorithm

I'm trying to understand the run-time analysis in the article [1]. The authors define the following notation: $g(n) = \hat O(f(n))$ if $g(n) = O(f(n)^{O(1)})$. In the run-time analysis of their ...
3
votes
1answer
33 views

Average Case Complexity Rivisted

I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem: Suppose we have a 5 elements array to be sorted using ...
4
votes
1answer
25 views

What is the average-case complexity of trial division?

The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, ...
4
votes
1answer
550 views

Matrix Max in less than O(n)

I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better ...
0
votes
0answers
40 views

Time complexity in relation to data size

Not sure if I completely understand this problem that was presented in class. We were given function $$f(n) = 2*f(n-1) + n$$ The base case for all these functions $f(1)$ is equal to 1. Assume $T(x)$ ...
0
votes
0answers
13 views

constant step-size assumption in non-asymptotic analysis of stochastic gradient descent

I have come across some non-asymptotic analysis of stochastic gradient descent algorithm (works of FRancis Bach https://hal.archives-ouvertes.fr/file/index/docid/831977/filename/newsto_hal.pdf) most ...
-1
votes
1answer
39 views

How is this algorithm average case derived?

For a simple linear search on an unsorted list my textbook says the following: To determine the average case, you add the number of iterations required to find the target at each possible position ...
3
votes
4answers
170 views
-1
votes
1answer
76 views

Running time of amstrong algorithm

I have a problem how to find best, worst, average case in armstrong number algorithm? Here the pseudo-code : ...
0
votes
1answer
34 views

run time analysis of a for loop [duplicate]

I am trying to prepare for a test comping up on run-time analysis. I have been hit with a for loop that is throwing me a bit. I am hoping someone can help me. the loop is ...
-2
votes
1answer
66 views

An algorithm for vertex cover

Let $G = (V,E) $ and let be $T \subseteq V$ . $T$ is called vertex cover if each edge of the graph is incident to at least one vertex of $T$ . Let be the following decisional problem : $PROBLEM$ ...
0
votes
3answers
110 views

How do I sort these elements in O(n) time?

So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix ...
-2
votes
1answer
76 views

Why do we use Insertion Sort in the Bucket Sort?

Bucket sort is a linear-time sort. Why do we use insertion sort in it? We know that insertion sort takes $O(n^2)$ time. Why can we not use any linear sort inside it? As we see, when in each bucket ...
0
votes
0answers
33 views

Time Complexity when loop variable depend upon outer loop variable [duplicate]

What is the time complexity of the following piece of code in worst case? ...
1
vote
1answer
62 views

How does the automatic complexity analysis of Codility work?

When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code. I was just wondering how ...
0
votes
1answer
58 views

Number of ways of making change in Big O notation

I have the following algorithm in ML: ...
4
votes
3answers
174 views

What is the time complexity of this atrocious algorithm?

This grew out of a discussion of deliberately bad algorithms; code credit to benneh on the xkcd forums. ...
0
votes
0answers
10 views

How to find the run time complexity of nested while loops? [duplicate]

So this problem is pretty nasty. I can easily find the number of iterations for each nested while loop. The first runs log_9(n) times and the second runs log_4(n) times. My problem that I do not ...
1
vote
0answers
35 views

Minimum exchanges for heap sort

I'm studying heap sort and was presented with the following question. What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
0
votes
0answers
14 views

Evaluate run time and compare these algorithms [duplicate]

Algorithm A divides the problem into 5 sub-problems of half the size. Solving each sub-problem then combining the solutions in linear time. Algorithm B solves problems of size n by dividing them into ...
3
votes
2answers
89 views

What is the average time complexity, for a single linked list, for performing an insert?

I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list. The longer the list, the longer it will take on average to do the ...
1
vote
1answer
52 views

Calculating execution time for recursive algorithm [duplicate]

How would I calculate the execution time, T(n), for this algorithm? ...
7
votes
2answers
313 views

What's the time complexity of this algorithm? And Why?

I am stuck by analyzing the time complexity of the following algorithm: ...
-1
votes
1answer
74 views

Worst case time complexity , please check whether my solution is correct? [closed]

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is __________. Options are $:$ ...
2
votes
2answers
53 views

Average-case analysis help

I am stuck on trying to understand how to solve the following question. Could someone please explain for a beginner to average-case analysis? Considering the following algorithm A which takes as ...
2
votes
1answer
39 views

Is this algorithm actually a graph-traversal algorithm?

I was given in a lecture the following algorithm that wwas said to be a graph-traversal algorithm. The algorithm given during the lecture The algorithm ...
3
votes
1answer
55 views

DFS vs. Union Find for computing connected components of a static graph

According to CLRS, When the edges of the graph are static—not changing over time—we can compute the connected components faster by using depth-first search. However, I tried to do some runtime ...
2
votes
1answer
81 views

For practical computing purposes, every algorithm is O(1)?

I am taking a course in algorithm analysis and the professor is arguing that using the negation of the definition for Big O, it can be argued that, for practical computing purposes, both the running ...
4
votes
1answer
99 views

What is the complexity of an in-place merge algorithm for forward iterators

I have written an in-place merge algorithm for forward iterators. My goal was to write an in-place merge algorithm to merge two sorted parts of a singly linked list without allocating extra memory to ...
0
votes
0answers
21 views

How to prove an algorithm with subroutines to belong to the polynomial time category using correct notation? [duplicate]

I'm having some trouble with writing my answer with the correct notation. I suppose I get the basic idea how to solve this and wrote down my answer but my gut tells me that that it's not ...
3
votes
3answers
76 views

Why is the running time of heapsort $O(n\log n)$?

Heapsort(A) 1 BUILD_MAX_HEAP(A) 2 for i=A.length downto 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize-1 5 MAX_HEAPIFY(A,1) In the book on ...
0
votes
0answers
6 views

Complexity of comparing each element of an array with other elements [duplicate]

Imagine we have an array of objects with arbitrary length. What level of complexity (like O(n) or O(n*m)) will exist if we want to check each element of the array with another elements in the array ...