For O(nlogn) why TLE for input size 10^5

help
1

My program uses divide and conquer strategy to find number of inversions.
(Similar to merge sort).

Time complexity is O(nlogn), still gives TLE for input size 100000.

problem - inversion count
solution - 7p81JM - Online C Compiler & Debugging Tool - Ideone.com

Please help me !!

2

Help me. Have I made mistake in calculating time complexity.
T(n) = 2T(n/2) + O(n).
O(n)- count function

So this recurrence ends to O(nlogn). still Im getting TLE

3

can someone please help! I have spend lot of time and now its hard to leave it unsolved and do other work.

4

You call THAT divide and conquer? You clearly have no idea what divide and conquer is. Learn that again then come back and ask later.
Small tip: This code is O(N ^ 2), not NlogN.

7

I understand , count function , is called ‘n’ times, and each time loop inside count function depends on size of ‘n’ and atmost runs in O(n).

BUT
I don’t understand ,on using standard Merge function( to combine sorted halves) instead of count function, how overall complexity reduces to nlogn. Merge function is also called ‘n’ times right( same as count function) and dependent on length of input.

9

Bro,
for T(n) = 2T(n/2) +O(n)
on solving…
ends
O(nlogn)

10

My bad… Let me check again.

11

I never use divide conquer in calculating inversions anyways, so if you want an insight on how the algorithm itself works you will have to search by yourself. This post is more of a “I don’t know how merge sort can be used to solve this task” than “This solution is O(nlogn) and it TLEs” now, just do some research.