Linked Questions

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
720 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
222 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
964 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
727 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
614 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
549 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
661 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

15 30 50 per page