The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote




What is the time complexity of the following code snippet? Assume x is a global variable and “statement” takes O(n) time?


asked in Algorithms by Active (2k points) | 88 views
T(n) = T(n/2) + O(n)

T(1) = O(1)

Solving this will give:-

T(n) = O(n). :)
I had a question. So there's a difference in 8T(n/2) + O(n) and 8*T(n/2) + O(n) ?
8T(n/2) will be when there are different 8 calls of function n. here 8 is getting multiplied only as a constant.
both are same 8T(n/2) + O(n) and 8*T(n/2) + O(n).

As mentioned above recurrence rlation will be T(n) = T(n/2) + n
Oh yes silly me. Thanks Rishabh and manu :)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,839 questions
36,693 answers
34,642 users