while (n >= 1)
n /= 2;
I am unable to get the Big-O notation for this
+1
A:
Any algorithm which cuts the problem in half each time is O(log(n)).
Shynthriir
2010-10-07 23:27:16
Generally when questions are tagged homework the idea is to give them hints to solve the question, and not outright give them the answer. This lets them understand the problem, which is the point of homework.
Paul
2010-10-07 23:29:20
would be awesome if you also give an explanation.
zengr
2010-10-07 23:29:48
If a teacher actually assigns a problem full credit having just the answer, I think something is wrong. Sometimes a problem is better understood when looking at the answer and working backwards, and then later problems become more understandable.
Shynthriir
2010-10-07 23:31:35
you should lead a student to a solution not give them the answer directly.
zengr
2010-10-07 23:33:43
+5
A:
I'll just follow Pointy's advice for the sake of exposition.
Try 8.
4 2 1 0: 4 iterations.
Try 32.
16 8 4 2 1 0: 6 iterations.
Try 66.
33 16 8 4 2 1 0: 7 iterations.
So… how are the initial numbers changing, and how are the numbers of iterations changing?
Potatoswatter
2010-10-07 23:27:38