# All Questions

16 questions
Filter by
Sorted by
Tagged with
4k views

### What does Θ(1) memory mean?

I have the definition of an in-situ algorithm from the professor, but I don't understand it. In-situ algorithms refer to algorithms that operate with Θ(1) memory. What does that mean?
7k views

### Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
2k views

### How can a quadratic algorithm be faster than a linearithmic one?

I have to solve the following problem: Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, ...
432 views

### Show that 6n^2 + 12n is O(n^2) [duplicate]

I understand how I would do this if the problem were as such $8n + 5$ is $O(n)$ $c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$ we ...
51 views

### Constant in Complexity of SQRT algorithm

this is my first question in CS so I apologize if this question is off-topic. If we use Newton`s Method for finding square root then complexity is $O(M(n))$ (using Wikipedia Notation: $M(n)$ is the ...
2k views

### Why does merge sort run in $O(n^2)$ time?

I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O ...
360 views

### Confusion regarding several time complexities including the logarithm

I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is: We use $O(\log n)$ complexity when there is division of any $n$ number on each ...
7k views

### What is an Efficient Algorithm?

From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
80 views

### How is this algorithm in these two complexities?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
14k views

### Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
5k views

### Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

I am reading section 6.4 on Heapsort algorithm in CLRS, page 160. ...
296 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
20k views

### Big O: Nested For Loop With Dependence

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
630 views

### Error in the use of asymptotic notation

I'm trying to understand what is wrong with the following proof of the following recurrence $$T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n$$  T(n) \leq 2\left(c\left\...
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 ...