Tag Info

New answers tagged

1

To calculate the height, you have to traverse tree, possibly by using recursion. To check that it is balanced, you have to traverse it exactly the same way. So these ways can probably be combined. I am tired and can't think of a good name for such a function right now, and I have a feeling the solution is ugly and there is probably a better way. But, it ...


2

If balanced means that the height is at most log_2(number_of_nodes) + 1, I suggest an algorithm could look like this: # define a tree tree := null | (left : tree, right : tree) # check if a tree is balanced is_balanced(tree) { maximum_height, number_of_elements = walk(tree) return maximum_height <= 1 + log_with_base_2(number_of_elements) } # ...


0

If you are asked for an "amortized constant time" algorithm, your algorithm may sometimes take a long time. For example, if you use std::vector in C++, such a vector may have allocated space for 10 objects, and when you allocate the 11th object, space for 20 objects is allocated, 10 objects are copied, and the 11th added, which takes considerable time. But ...


14

The question seems to specifically ask for constant time, and not an amortized constant time. So with respect to the quoted question, no, they are not effectively the same*. Are they however in real world applications? The typical issue with amortized constant is that occasionally you have to pay the accumulated debt. So while inserts are generally ...


9

Amortized Constant Time can almost always be considered equivalent to Constant Time, and without knowing the specifics of your application and the type of usage you are planning to do to this queue, most chances are that you will be covered. An array list has the concept of capacity, which is basically equal to the largest size/length/count of items that ...


6

It depends – on whether you are optimizing for throughput or for latency: Latency-sensitive systems need consistent performance. For such a scenario, we have to emphasize worst-case behaviour of the system. Examples are soft real time systems such as games that want to achieve a consistent framerate, or web servers that have to send a response within a ...


-2

A good place to start might be the Algorithms class on Coursera. You will get a broad overview of some important algorithms and data structures, video lectures, programming exercises, theory problems, and you can look at the references for more pointed information on certain problem. https://class.coursera.org/algo-007


0

Analyzing complex algorithms requires lot mathematical background. For a refresher on analysis of standard algorithms you can refer to books. If you need a starting point for analysis of algorithms i would suggest to read some books on algorithms. The best book i can refer for analyzing algorithms is Introduction to Algorithms. If you would like to attend ...


-1

What you can try is to find the analytical expression that is equal to the cost of the algorithm you are working with. In many cases, this expression might be a sum (usually for nested loops). However, for a recursive algorithm, you might express it's cost with a recursive formula that you will have to solve. For example, the cost of a binary search may be ...



Top 50 recent answers are included