0 votes 0 votes closed as a duplicate of: GATE CSE 2023 | Question: 44 Time complexity f( ) { while(n>1) { for (i = 1 to n) { } n = n/2 } } g ( ) { for (i = 1 to 100n) { } } $f(x)=O(g(x))$ $f(x)=\theta(g(x))$ $f(x)=o(g(x))$ $f(x)=\omega(g(x))$ Algorithms memorybased-gatecse2023 goclasses algorithms time-complexity multiple-selects + – GO Classes asked Feb 5, 2023 • closed Feb 20, 2023 by Lakshman Bhaiya GO Classes 1.5k views comment Share Follow See all 5 Comments See all 5 5 Comments reply lolalo commented Feb 6, 2023 reply Follow Share the time complexity of f is O(nlogn) and for g is O(n). –1 votes –1 votes Hira Thakur commented Feb 6, 2023 reply Follow Share jomboy how $f(n)=nlogn$? it should be $f(n)=n$ because $T(n)=T(\frac{n}{2})+n$ . every time it will be divided by $n/2^k$ form. 0 votes 0 votes lolalo commented Feb 6, 2023 reply Follow Share @Hira Thakur, I just thought that while loop is running log(n) times and the inner for loop is running n times. so nlogn. I must be wrong about this process then. 1 votes 1 votes akshaw commented Feb 9, 2023 reply Follow Share @GO Classes please fix the formatting of the question. 0 votes 0 votes Deepak Poonia commented Feb 9, 2023 reply Follow Share The formatting of the question has been corrected.Answer will be Option $A,B.$$f(x) = \Theta(x)$ ; $g(x) = \Theta(x)$So, $f(x) \in \Theta(g(x))$ and $f(x) \in O(g(x))$Video Solution:Algo: Two functions' Comparison 1 votes 1 votes Please log in or register to add a comment.