Linked Questions

195 votes
3 answers
26k 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 ...
Raphael's user avatar
  • 72.4k
3 votes
2 answers
255 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 ...
user avatar
-1 votes
1 answer
192 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 ...
user's user avatar
  • 129
2 votes
1 answer
115 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 ...
Johnnie's user avatar
  • 21
1 vote
1 answer
144 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 ...
Alpha Mineron's user avatar
0 votes
0 answers
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 ...
ykh's user avatar
  • 109
101 votes
3 answers
35k 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 ...
Jack H's user avatar
  • 1,323
4 votes
2 answers
35k 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, ...
Mahdi Khosravi's user avatar
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 ...
Shivam Naik's user avatar
11 votes
2 answers
711 views

How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?

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 >...
Andre Resende's user avatar
0 votes
2 answers
3k 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 ...
user avatar
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)$ ...
Computernerd's user avatar
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 ...
Pankaj Sejwal's user avatar
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 ...
bandit_king28's user avatar
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: ...
Sonu Jha's user avatar
  • 111
5 votes
2 answers
571 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.
PancakeOverflow's user avatar
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....
apnorton's user avatar
  • 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 ...
Dave's user avatar
  • 495
4 votes
1 answer
2k 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 ...
Юрій Ярош's user avatar
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); } ...
user1917769's user avatar
3 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 ...
GreatDuke's user avatar
  • 131
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 ...
Aisha Ashwal's user avatar
4 votes
2 answers
719 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 ...
user avatar
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 ...
Sid's user avatar
  • 355
1 vote
2 answers
216 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 ...
Tobi Alafin's user avatar
  • 1,617
1 vote
2 answers
959 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 ...
Programmer's user avatar
8 votes
1 answer
684 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 ...
user85798's user avatar
0 votes
1 answer
607 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 ...
Jesus Salas's user avatar
1 vote
1 answer
512 views

Computational complexity of generating a random vector

I'm new to the concept of computational complexity and trying to understand the topic in depth. I went through some references mentioned by some old questions, however, I had this question and not ...
Chao's user avatar
  • 13
0 votes
0 answers
643 views

Implement Immediate Smaller Element problem using Stack

Immediate Smaller Element Problem: Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
salazarin's user avatar
  • 101
3 votes
2 answers
82 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 ...
fvrghl's user avatar
  • 141
0 votes
2 answers
104 views

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

This question is specifically related to https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits ...
Jeff's user avatar
  • 113
2 votes
1 answer
56 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{...
sequence's user avatar
  • 131
1 vote
1 answer
125 views

Big-O in computer Science [duplicate]

As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
user avatar
0 votes
1 answer
141 views

Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
Ben Harris's user avatar
0 votes
1 answer
60 views

Reccurrence equation and finding suitable algorithm

I'm given the following recurrence equation: $$\begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && \...
threaz's user avatar
  • 103
0 votes
1 answer
81 views

Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
BAM's user avatar
  • 143
1 vote
1 answer
61 views

How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book ...
heretoinfinity's user avatar
0 votes
0 answers
70 views

Time complexity of this for-loop

I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part. ...
John Smith's user avatar
1 vote
0 answers
66 views

Big-Oh of algorithm

I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345. The algorithm looks like: ...
FreeStyle4's user avatar
0 votes
0 answers
31 views

Am I doing this correctly? Recurrence Relations [duplicate]

The function is this: ...
Connal Sumlin's user avatar
0 votes
0 answers
19 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++) ...
new's user avatar
  • 1