5
Every algorithm with complexity involving a "log" has recursion involved? Type: O(n log n). If not, when will you have "log" in some complexity?
1 answer
2
What it is exactly to say that we have something with complexity log n ?
Let’s say you have a balanced tree with 32 - 1 elements.
This tree has 4 levels, if you want to add a new level, will practically double its size (64 - 1 elements) but its search time grows at a very low ratio compared to that (logarithmic ratio)because now at worst instead of using 4 steps to find the result we will have to do 5 steps. Compared to the other reasons of complexity is a very good result (this question/answer is a good reference), here you may have an idea of the complexity of the most popular algorithms.
Now to the point of the question log(n)/log(i) is a solution with respect to recurrence.
f(n) = f(n/i) + c
It happens every time a function can be written recursively where the parameter size is divided by a constant in each iteration, as in:
funcao(entrada, n){
//faça algo aqui
retorne funcao(entrada, n/constante);
}
So then we say that complexity θ(log(n)).
Examples:
- When you search in a balanced tree: start at the root if the value of
nfor Gual return node (constant), otherwise if it is smaller go to the left side of the tree (size/2), if it is larger go to the right side (size/2). - Exponentiation:
a^n: if n = 1 then returna, otherwisea^(n/2)(elevateaat halfn) = b (sizen/2), multiplybforband go back to the beginning.
Browser other questions tagged algorithm
You are not signed in. Login or sign up in order to post.
Explain it better there.
– Maniero
I guess that example didn’t make much sense to question.
– pmargreff
Usually algorithms that have complexity with log(n) is because it involves binary search (divide and Conquer). Many who have recursion involve this technique. But no, there are algorithms with log(n) that are not recursive, for example finding an element in an ordered vector.
– Sérgio Mucciaccia
Hello @Sérgiomucciaccia in your case you gave an example of something that could be implemented recursively, I think the idea of the question is to discover something that is not possible to do recursively and still has complexity log(n) ...
– pmargreff
There is an implementation of an algorithm that has log in complexity and has no recursion involved. So the statement as it was made is false, because not every algorithm necessarily satisfies this condition. Well, this is what I understood from the question. Now with its interpretation really, any log algorithm involved can be implemented with recursion, so the affirmative would be true. For me if it can be implemented without recursiveness then there is no recursiveness involved (it can have but not necessarily have). But there is already a question of the interpretation of each one.
– Sérgio Mucciaccia
An algorithm O(log n) or O(n log n) is probably of the type "divide and conquer", which CAN be implemented recursively, it does not mean that it must or must be.
– epx