Why it is not O(n*logn)


#1

Why it is not O(n*logn) please anyone can tell me


#2

Bro…try to understand this problem in terms of simple nxn matrix. Whenever you want to iterate through the entire matrix what happens simply for every outer loop ieration we go on as n+n+n+…n times in inner loop, whose gp sum is n x first term which is n here. So time complexity is O(n^2). Now in this case we are going on for every outer loop iteration as n+n/2+n/4+…n times in inner loop, whose gp sum is 2n. So the time complexity is O(n). I hope you got this thing.


#3

I think outer loop runs infinite times.

So overall complexity becomes N(1 + 1/2 +1/4 + …upto infinity)

T(n) = N(sum of infinite terms in GP)
=N(1/1-0.5)
=2N
Therefore O(N)