25k views

### Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
• 71.6k
34k views

### How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
• 1,313
687 views

This a homework question from Udi Manber's book. Any hint would be nice :) I must show that: $n(\log_3(n))^5 = O(n^{1.2})$ I tried using Theorem 3.1 of book: $f(n)^c = O(a^{f(n)})$ (for $c >... 8 votes 1 answer 493 views ### What counts as an operation? Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all ... 5 votes 2 answers 569 views ### BigO, Running Time, Invariants - Learning Resources What are some good online resources that will help me better understand BigO notation, running time & invariants? I'm looking for lectures, interactive examples if possible. 4 votes 2 answers 34k views ### Time complexity of a backtrack algorithm I've developed the following backtrack algorithm, and I'm trying to find out it time complexity. A set of$K$integers defines a set of modular distances between all pairs of them. In this algorithm, ... 4 votes 2 answers 715 views ### Analysis of algorithms, 'big O' question The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation? Also, what about ... 4 votes 1 answer 1k views ### What are elementary operations in time complexity definition? Wikipedia gives us the following defintion of time complexity: "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an ... • 153 3 votes 2 answers 15k views ### How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms? How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ... • 129 3 votes 2 answers 5k views ### What is running time of an algorithm? What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ... 3 votes 2 answers 81 views ### How to include calls to an$O(n)$subroutine on finite-sized inputs in an analysis? I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the ... • 141 3 votes 2 answers 6k views ### Using software to calculate the complexity of an algorithm I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ... 3 votes 1 answer 2k views ### Finding growth of "inter-recursive" functions consider following code int f(int x) { if(x<1) return 1; else return f(x-1)+g(x); } int g(int x) { if(x<2) return 1; else return f(x-1)+g(x/2); } ... • 291 3 votes 2 answers 252 views ### Determining Big O [duplicate] i<--2 while (i<n) someWork (...) i <-- power (i,2) done Given that someWork(...) is an O(n) algorithm, what is the worst case ... 2 votes 1 answer 52 views ### Proving complexity of computing product of matrices If$A$is a non-singular$n\times n$matrix,$B$is an$n\times p$matrix, and$C$is a$p\times n$matrix (where$1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is$\frac{...
• 131

15 30 50 per page