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
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 ...
151 views

### How to get an O(n) for a search algorithm [duplicate]

Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case. At the ...
• 129
114 views

### Analysis of Algorithms: Applying Concepts [duplicate]

I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application. I ...
• 21
1 vote
143 views

### What exactly is bigO notation? [duplicate]

I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent? I heard that there are two: RunTime Memory Complexity How can I learn ...
82 views

### How to calculate Complexity Time O()? [duplicate]

Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was. I can solve basic problems, but whenever the problem ...
• 109
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
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, ...
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
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 >... 0 votes 2 answers 2k views ### how to calculate time complexity of non terminating loops I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs. I just wondered that how to calculate time complexity of non terminating ... 0 votes 4 answers 5k views ### Proving Quicksort has a worst case of O(n²) I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is$O(n^2)$... • 649 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 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 ... 1 vote 2 answers 3k views ### Worst case time complexity of heap sort I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows: ... • 111 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. 2 votes 1 answer 3k views ### Upper Bound on Runtime of Memoized DP Algorithms I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions.... • 254 1 vote 2 answers 2k views ### How to connect the math of recurrence relations to daily programming concepts What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear ... • 485 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 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 2 votes 2 answers 2k views ### Recurrence for quaternary search algorithm I have to come up with the recurrence for the quaternary search algorithm. My initial thought is$T(n)=4T(\frac{n}{4})+c$because the algorithm examines all four subproblems, and each is one quarter ... 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 ... 2 votes 2 answers 1k views ### Finding integer square root for large integers [find asymptotic time complexity] So I found this tasks in one book I am practicing from where it says: "Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time ... • 121 1 vote 1 answer 1k views ### Memoized Palindrome Subsequence I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following ... • 355 1 vote 2 answers 211 views ### Reasoning on Efficiency (2) Two algorithms to solve a particular problem can have theur efficiency compared using the$O$and$o$notation. However, this is very crude method, and tells us no information on how more effective ... • 1,597 1 vote 2 answers 903 views ### How to find the big o running time if the recursion function have different cases of recursion with different fraction of n? How to find the big o running time if the recursion function have different cases of recursion with different fraction of n? If I have a recursive function like this for example (This is just an ... 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 ... 0 votes 1 answer 566 views ### Algorithm Time complexity analysis for algorithm having two different time complexities I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to$N$(set length) and$M$(bits to represent the numbers). I'm having some ... • 519 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
1 vote