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

learn more… | top users | synonyms

0
votes
0answers
4 views

Complexity of Recursive Function

We have to recursive function first one is $\left\{ \begin{array}{l l} T(n) = \sqrt{n} T(\sqrt{n}) + n \\ T(1) = 1 \end{array} \right.$ and the second one $\left\{ \begin{array}{l ...
0
votes
0answers
21 views

Proof of the base case of Big Theta using induction

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
3
votes
1answer
31 views

Where would someone find amortized analysis more useful than average analysis and the opposite?

I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing ...
1
vote
1answer
54 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
8
votes
1answer
166 views

Solving recurrence relation with two recursive calls

I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very. In order to do this I ask myself the question ...
0
votes
1answer
50 views

To know time complexity of some code

What is the time complexity of following piece of code in terms of number of updates to S in worst case. ...
-2
votes
0answers
17 views

Minimum time intervals to fully random access an array?

Suppose that i have an array $T$ of $k$ possitions. I have a random access policy. Each array element can be accessed with equal probability $\frac{1}{k}$ at each time interval $t$. My question is how ...
0
votes
1answer
35 views

Creating all possible subsets and complexity calculation [duplicate]

I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm. Now I would like ...
1
vote
1answer
49 views

Order of a pseudo code

I am trying to find order of an bellow algorithm but I have no idea about, the problem like below we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in ...
1
vote
1answer
62 views

What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?

Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of ...
2
votes
1answer
38 views

How do we analyze Algorithms with parallelism features

As I am comparing between two algorithms, I was wondering which is the best approach to use to compare between the both. Big-O seems not the perfect metric for me, as the it's based on the worst-case, ...
0
votes
0answers
14 views

Cache lines to store an $s \times s$ matrix

I am reading Frigo's "Cache Oblivious Algorithms" paper. On page3 near the bottom, it says: An $s \times s$ submatrix is stored on $\Theta (s + s^2 / \mathcal{B})$ cache lines. Why is this so? ...
1
vote
0answers
42 views

Prove the correctness of Tarjan's off-line least-common-ancestors algorithm

Tarjan's off-line least-common-ancestors algorithm is given as follows: LCA($u$) Make-Set($u$) Find-Set($u$).$ancestor$ = $u$ for each child $v$ of $u$ in $T$ $\quad$ LCA($v$) ...
-1
votes
0answers
10 views

Binary Search Algorithm [duplicate]

We want to know whether a sorted array of size 17 contains a key K. Using Binary Search, what will be the FEWEST number of array elements we will need to examine (in the worst case)?
-1
votes
0answers
19 views

Calculating the number of calls to a recursive algorithm [duplicate]

A(n): if n > 0 then A(n − 1) print “Hello” A(n − 1) How many times does "Hello" get printed when ...
4
votes
3answers
54 views

Is there a technique for statically checking that a function is only called at a particular rate?

I was reading this article about types, and started wondering how static type checkers could enforce other properties in programs. For example, say I wanted to create a language which would allow ...
0
votes
0answers
14 views

Big o notation for the algo [duplicate]

Asked this at programmers Stack Exchange, was recommend to ask here : What would be the big o for the algo: for (i=0; i < n*n; i++) for(j=0; j<i*i; j++) ...
-2
votes
0answers
15 views

Number of nodes in a B-Tree

How many nodes does a resulting B-Tree(min degree 2) have if I insert numbers from 1 to n in order? I tried inserting nodes from 1 to 20 there was a series for the number of nodes coming but i could ...
2
votes
0answers
34 views

Frigo's cache-oblivious algorithms paper

I am reading Frigo's "Cache-Oblivious Algorithms" paper and I need help understanding his cache complexity expressions for the base cases. He starts on page 3 with "An $s \times s$ submatrix is ...
0
votes
1answer
47 views

Time Complexity for matrix multiplication? [duplicate]

How can I find out the time complexity for the brute-force implementation of matrix multiplication for: Two square matrices ($n \times n$), Two rectangular matrices ($m \times n$) and ($n \times ...
2
votes
0answers
31 views

Constant in Complexity of SQRT algorithm

this is my first question in CS so I apologize if this question is off-topic. If we use Newton`s Method for finding square root then complexity is $O(M(n))$ (using Wikipedia Notation: $M(n)$ is the ...
2
votes
1answer
38 views

What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a ...
0
votes
0answers
29 views
-2
votes
1answer
38 views

Asking for help with this Therac 25 bugged code. I don't understand the explanation

Therac 25 is a radiation therapy machine that lead to 3 deaths and 3 injuries in 1980s. That's the worst accidents in history which are caused by software bugs. In 1993, Leveson and Turner did a ...
0
votes
1answer
96 views

What is the runtime of the following code? [duplicate]

Can you explain to me how you get the Big O notation for the runtime of the following snippet of code? ...
1
vote
0answers
50 views

Influence of edge number and priority-queue implementation on the runtime of Dijkstra

When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
0
votes
0answers
69 views

stuck on proving the optimality of a greedy algorithm [closed]

I'm Ph.D. student doing research in wireless networks. My past projects are more oriented to systems than theory. For my current project, I devised a greedy algorithm for an optimization problem. ...
1
vote
0answers
52 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
0
votes
0answers
26 views

analyzing moving pseudorandom sieve algorithm [closed]

the following is a rough simpification or "toy" version/ abstraction/ model (but still quite nontrivial) for/ inspired by a famous open math problem (which for now will remain nameless & may be ...
0
votes
1answer
39 views

Maximum value a variable can hold without documentation [closed]

Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data ...
6
votes
1answer
63 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
0
votes
1answer
22 views

Understanding when to count key comparisons

I understand that for something like Linear search, this would be the key comparison: if(itemToFind == a[i]) return i; If I put this method into another ...
0
votes
1answer
27 views

Comparing Big O Complexity [duplicate]

I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although ...
0
votes
2answers
75 views

How to show that this algorithm for evaluating polynomials works?

I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..." How do I exactly show ...
3
votes
0answers
20 views

Pruned FFT runtime

Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). ...
0
votes
1answer
47 views

Showing that tournament sort requrires O(n log n) comparisons

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...
2
votes
1answer
36 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
27
votes
3answers
5k views

Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', ...
1
vote
1answer
40 views

What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?

Background: The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half). Pool Ball Problem: Given ...
-1
votes
1answer
33 views

Proving number of calls made in cut-rod algorithm [duplicate]

I was reading dynamic programming chapter from famous book Introduction To Algorithm In rod cutting problem it gives simple algorithm as follows: ...
1
vote
1answer
34 views

How to find expected number of slots of a certain size k in hash table?

If you can make no assumptions about the hash function, how can you find the expected number of slots of certain size k in a hash table? Looking more for a theoretical proof type of answer than a ...
1
vote
1answer
76 views

Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
42
votes
11answers
5k views

How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
-3
votes
1answer
67 views

Probabilty that quicksort partition creates an imbalanced partition

I have come across this question: Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
-1
votes
1answer
58 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
0
votes
0answers
20 views

Programming and evaluating sorting algorithms based on its complexity [duplicate]

I need to program and evaluate two sorting algorithms: insertion sort and merge sort I know that the complexity of insertion sort is O(n^2) and for the merge sort is O(n·log n) In this case I have a ...
0
votes
0answers
19 views

How to conduct time complexity analysis for an implemented algorithm [duplicate]

Main task In my bachelor degree's thesis I've developed an algorithm for recommender systems which uses personalized PageRank with some particular features as nodes. In the recommender systems' ...
1
vote
2answers
45 views

Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]

Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
0
votes
1answer
55 views

tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
0
votes
0answers
10 views

How to calculate the complexity of Uniform Binary Search algorithm [duplicate]

I was studying the Uniform Binary Search algorithm authored by Donald Knuth which is an optimization of the classic Binary Search algorithm. Can someone explain the complexity analysis for Uniform ...