solve this recurrence relation

Question

T(n) = T(n^1/2) + n

doing this in substitution method gives the ans as O(n)

but using tree recursion gives the ans as O(nlogn)

which of these are correct and which has to be considered for worst case

Answer 1

First of all, no matter which method you use, you will get the same answer. Secondly, you have not provided the base case.