145 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.&...
71 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. ...
• 125
668 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 ...
• 101
1 vote
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 ...
1 vote
557 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 ...
• 13
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 ...
• 153
1 vote
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 ...
733 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 ...
1 vote
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
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 ...
• 113
1 vote
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 ...
1 vote
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: ...
1 vote
223 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,617
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 ...
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 ...