2 votes 2 votes What is the time complexity of the following code snippet? Assume x is a global variable and “statement” takes O(n) time? Algorithms time-complexity algorithms asymptotic-notation recursion + – Warlock lord asked Sep 11, 2017 Warlock lord 821 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Rishabh Gupta 2 commented Sep 11, 2017 reply Follow Share T(n) = T(n/2) + O(n) T(1) = O(1) Solving this will give:- T(n) = O(n). :) 0 votes 0 votes Warlock lord commented Sep 11, 2017 reply Follow Share I had a question. So there's a difference in 8T(n/2) + O(n) and 8*T(n/2) + O(n) ? 0 votes 0 votes Manu Thakur commented Sep 11, 2017 reply Follow Share 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 0 votes 0 votes Warlock lord commented Sep 11, 2017 reply Follow Share Oh yes silly me. Thanks Rishabh and manu :) 0 votes 0 votes prem6346 commented Dec 14, 2017 reply Follow Share why cant it be T(n)=T(n/2)+c 0 votes 0 votes Mohit Kumar 6 commented Apr 17, 2020 reply Follow Share because statement(which is written in code ) take O(n) time question say. 0 votes 0 votes Please log in or register to add a comment.