How to know when Big O is Logarithmic?

algorithm math big-o recurrence logarithm
Léo Léopold Hertz 준영 picture Léo Léopold Hertz 준영 · Apr 15, 2009 · Viewed 7.2k times · Source

My question arises from the post "Plain English Explanation of Big O". I don't know the exact meaning for logarithmic complexity. I know that I can make a regression between the time and the number of operations and calculate the X-squared value, and determine so the complexity. However, I want to know a method to determine it quickly on paper.

How do you determine logarithmic complexity? Are there some good benchmarks?

Answer

Mitch Wheat picture Mitch Wheat · Apr 15, 2009

Not rigorous, but it you have an algorithm that is essentially dividing the work needed to be done by half on each iteration, then you have logarithmic complexity. The classic example is binary search.

Related questions

Reccurrence T(n) = T(n^(1/2)) + 1

I've been looking at this reccurrence and wanted to check if I was taking the right approach. T(n) = T(n^(1/2)) + 1 = T(n^(1/4)) + 1 + 1 = T(n^(1/8)) + 1 + 1 + 1 ... = 1 + 1 + 1 + ... + 1 (a total of rad n times) = n^(1/2) So the answer would come to theta bound …

Read More
Solving a recurrence T(n) = 2T(n/2) + n^4

I am studying using the MIT Courseware and the CLRS book Introduction to Algorithms. I am currently trying to solve the recurrence (from page 107) T(n) = 2T(n/2) + n4 If I make a recurrence tree, I get: Level 0: n4 Level 1 2(…

Read More
Solving the recurrence T(n) = 2T(sqrt(n))

I would like to solve the following recurrence relation: T(n) = 2T(√n); I'm guessing that T(n) = O(log log n), but I'm not sure how to prove this. How would I show that this recurrence solves to O(…

Read More