Linked Questions

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.&...
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. ...
• 125
0 votes
0 answers
644 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
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 ...
1 vote
1 answer
515 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
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 ...
• 153
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 ...
8 votes
1 answer
688 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
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
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 ...
• 113
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 ...
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: ...
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 ...
• 1,617
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 ...
0 votes
1 answer
608 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

15 30 50 per page