2 votes 2 votes which function will grow faster? a) x$\sqrt{x}$ b) x! Algorithms algorithms time-complexity + – hacker16 asked Jan 20, 2018 hacker16 487 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Mk Utkarsh commented Jan 20, 2018 i reshown by Mk Utkarsh Jan 20, 2018 reply Follow Share BLUE $\Rightarrow$ x! Red $\Rightarrow$ x√x x! grows faster 0 votes 0 votes srivivek95 commented Jan 20, 2018 reply Follow Share x!=x (x-1) (x-2)....3.2.1=O(xx) Now, compare xx and xsqrt(x) xx will grow faster 0 votes 0 votes MiNiPanda commented Jan 20, 2018 reply Follow Share Take log on both sides.. √xlogx and log(x!) log(x!) Can be written as xlogx( you can search the derivation ) So, √xlogx and xlogx B is greater.. 0 votes 0 votes sumit goyal 1 commented Jan 20, 2018 reply Follow Share @MiNiPanda yes youre right , i heard sometime taking log it can give incorrect result , thats why i avoid using it , since by taking log it decreases the rate of function exponentially , how we will sure that , here rate is not decreased exponentially 0 votes 0 votes MiNiPanda commented Jan 20, 2018 reply Follow Share It gives incorrect result only when both sides become equal. In this case if both would have come xlogx then it would have been incorrect to infer that both have same rate of growth. In that case other ways should be followed. But if they are different then it's okay... 0 votes 0 votes sumit goyal 1 commented Jan 20, 2018 reply Follow Share like n^2 and n are not theta of each other , but if i took log , then 2logn and logn are theta of each other thanks @MiNiPanda 0 votes 0 votes Mk Utkarsh commented Jan 20, 2018 reply Follow Share Approximation for logn! $\approx$ (n+1)logn - n by Srinivasa Ramanujan :o 0 votes 0 votes MiNiPanda commented Jan 20, 2018 reply Follow Share Right Sumit :D Utkarsh ooh..maybe .. but that again can be approximated to nlogn for asymptomatic analysis.. 1 votes 1 votes Please log in or register to add a comment.