# Tagged Questions

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

47 views

### What is the complexity of Array[n] and Object.value

I faced a great doubt about the Complexity of two ways of calling a information. First I have an Array, if I call an array in a program like this: print array[0] ...
71 views

### Estimating the complexity of an algorithm by looking at code

Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better ...
35 views

### Why does using unary in subset sum problem result polynomial time complexity?

From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input). The number of bits in binary notation is obviously less ...
83 views

### Time complexity of Depth First Search

Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about. I ...
58 views

### Running time of naive recursive implementation of unbounded knapsack problem

How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more ...
59 views

### Long multiplication school method: number of primitive operations to calculate first partial product?

Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long ...
50 views

### Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements?

Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why? How would one justify the answer to the above ...
105 views

### What is the compleixty of this algorithm?

The algorithm is as follows: a = rand % a random number between 0 and 1 b = a while b == a b = rand end Here rand is a ...
55 views

### Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
32 views

### Amortised analysis of a simple loop and 3 operations

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. Operation OP(S,X[i]) has complexity ...
53 views

### What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
58 views

### runtime of problems vs algorithms

I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation? Also, ...
50 views

### With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
23 views

### Amortised complexity of dynamic array using potential function

I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can ...
43 views

### Complexity and number of bits of square root number

Let an integer a, and b is the number of bits a. 1) If I have a number ...
37 views

### Time complexity for Breadth-First search

I would like to know why the average number of nodes at level d in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here b is the branching factor of the tree and d is the ...
34 views

### Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input ...
46 views

### Generally, does the time it takes to compute (n mod m) depend on the size of n?

Example: Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits. Would the speed of the computation a mod m vary greatly from b mod m because of ...
35 views

### Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
61 views

### Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
37 views

### Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
29 views

### Time complexity of nested for loop function involving mod to filter out the execution [duplicate]

I have to find the time complexity of the following program: ...
74 views

### What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking. ...
72 views

### Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

I am currently learning landau notations and am stuck on the following True/False question. What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. ...
28 views

### Runtime analysis with recursion factor

I have this code: if n is even { for i=1....n for j=1...i print j return 8*foo(n/2) } Asking to calculate the running time $T (n)$. I thought at first ...
36 views

### Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
36 views

### Runtime of this function: $T(n) = 8T(n/3)+nlogn$

I need to find the runtime of this function: $$T(n) = 8T(n/3)+nlogn$$ I try to use the "Master Theorem" when $$a=8,b=3$$ $$n^{log_ba}=n^{log_38}$$ $$f(n)=nlogn$$ And I define: \varepsilon = -1.5+...
36 views

### CFL that runs in NP-time

What is an example of a context-free language that runs in NP-time? I've done searches but cant find one. Frankly, I do not know how to determine when a CFL is P or NP. Can someone tell me, please?