Complexity of Algorithms

What exactly is it to say that we have something with log n complexity?

Let's say you have a balanced tree with 32 - 1 elements.

Thistreehas4levels,ifyouwanttoaddanewlevel,itwillpracticallydoubleitssize(64-1elements)butitssearchtimegrowsataverylowratiocomparedtothis(logarithmicreason),becausenowintheworstcaseinsteadofusing4stepstofindtheresultwewillhavetodo5steps.Comparedtotheotherreasonsofcomplexityitisaverygoodresult(#), here you can get an idea of the complexity of the most popular algorithms .

Now going 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 size of the parameter is divided by a constant in each iteration, as in:

funcao(entrada, n){
 //faça algo aqui
 retorne funcao(entrada, n/constante);
}

Then we say that the complexity θ(log(n)) .

Examples:

• When you search on a balanced tree : start at the root, if the value of n is If it is smaller then go to the left side of the tree (size / 2), if it is larger go to the right side (size / 2).
• Exponentiation: a^n : case n = 1 then return a , otherwise a^(n/2) (raise a to half n ) = b ( n/2 size), multiply b by b and go back to the beginning.

Translated from SO - in

Source 1 + Image

Font 2