How to calculate the growth order of an algorithm?

R

RokkerRuslan2014-02-27 20:28:36

Mathematics

RokkerRuslan, 2014-02-27 20:28:36

Let's say two algorithms are given: Golden section method and Bisection method , how to find their growth order (by the number of steps)?

Reply

Answer the question

In order to leave comments, you need to log in

2 answer(s)

S

Sergey, 2014-02-27
@begemot_sun

Your algorithms are essentially the same thing. Just in the first segment is divided in proportion to the golden section, and in the second case, the segment is divided in half.
Both have O(log n) complexity.

K

Killy, 2014-02-27
@Killy

If the question is how exactly the complexity estimate for an arbitrary algorithm is derived, then google about the Computational Complexity of Algorithms, Complexity Theory.
Something like this: www.structur.h1.ru/ocenka.htm