Is there a way to tell whether a subroutine has runtime log(n)?

Question

Usually the rule is that if there is a loop of 1 to n elements then the complexity is O(n), and further nested loops are n x O(n). However, when do we say if a subroutine has complexity O(log n)?

Check: http://stackoverflow.com/a/16785817/2128327 – Khaled.K May 28 '13 at 07:10 — Khaled.K, May 28 '13 at 07:10
No need to downvote my question... – Evil Washing Machine May 28 '13 at 16:21 — Evil Washing Machine, May 28 '13 at 16:21

score 1 · Answer 1 · edited May 23 '17 at 12:05

1

You can take as first example binary search. A explanation of the complexity of this algorithm can be taken from a related question how to calculate binary search complexity. It shown that the calculation of this type of complexity can be obtain from the recurrence.

edited May 23 '17 at 12:05

Community

1
1

answered May 27 '13 at 20:35

Mihai8

3,113
1
21
31

Mzf · Accepted Answer · 2013-05-28T17:10:22.363

1

When in each iteration we reduce the problem size be a factor of X , we can say that the problem is O(log n)

E.g - Binary Search: in each iteration we reduce the problem size by factor of 2

edited May 28 '13 at 17:10

answered May 27 '13 at 20:51

Mzf

5,210
2
24
37

Is there a way to tell whether a subroutine has runtime log(n)?

2 Answers2