Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
8
votes
0answers
228 views

Complexity of computer algebra for systems of trigonometric equations

As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence: $\qquad f_{p_0} = 0\\ \...
1
vote
1answer
386 views

Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...
11
votes
2answers
3k views

Hashing using search trees instead of lists

I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
4
votes
2answers
3k views

Running time - Linked Lists Polynomial

I have developed two algorithms and now they are asking me to find their running time. The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are ...
5
votes
2answers
554 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.