Linked Questions

36
votes
5answers
97k views

How to come up with the runtime of algorithms? [duplicate]

I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site. I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
0
votes
2answers
7k views

Using induction to prove a big O notation [duplicate]

I'm trying to prove that the following recurrence relation has a runtime of O(n): fac(0) = 1 fac(n+1) = (n + 1) * fac(n) ...
0
votes
0answers
9k 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 r$)?
2
votes
3answers
1k views

Analysis of very simple algorithm [duplicate]

I need to find the time complexity of the following simple algorithm. Calculate the time complexity of the following algorithm: ...
2
votes
1answer
2k views

What is the time complexity of binary sum (recursion) [duplicate]

Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions. There is an ...
2
votes
1answer
415 views

Big O Algorithm Analysis [duplicate]

I'm confused about the complexity of the following code: for(i=1; i<=n; i = 2*i) for(j=1; j<=i; j++) print A[j] I know that the first loop is ...
-2
votes
1answer
2k 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. ...
0
votes
1answer
2k 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 ...
0
votes
2answers
190 views

When to add and when to multiply to find time complexity [duplicate]

I am trying to learn how to determine time complexity. Sometimes, I see complexity as $\log n + \log n = 2\log n$ but sometimes I see complexity as $\log n\cdot\log n$ which is $(\log n)^2$. Suppose ...
1
vote
1answer
1k views

Explanation of the complexity of a loop [duplicate]

I am confused on the following: In the following trivial code: ...
1
vote
2answers
2k views

Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the ...
-1
votes
2answers
2k views
0
votes
2answers
2k views

What is the asymptotic running time of the following piece of code? [duplicate]

I am working with this problem: What is the asymptotic running time of the following piece of code? ...
-1
votes
2answers
320 views

What will be the time complexity for the following search algorithm in a graph? [duplicate]

I have a graph which looks something like below I am searching for a given string s going down such that at every node it makes a decision (either to visit the ...
-1
votes
1answer
806 views

Converting pseudo code to a recurrence relation equation? [duplicate]

The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(n) ...

15 30 50 per page