How to calculate time complexity for sum of four (CSES problemset)

Revision en3, by Mr_No_One, 2020-06-14 15:26:51

I am solving a question from CSES sum of four values. I found out the time complexity to be O(n^3) and n is 1000. But most of the solutions are within 0.12 seconds. Where I am going wrong with the calculation of time complexity.

Question is :: You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x. CSES question link

The approach i am using is to store index of each element in unordered_map and then traverse the array using three loops to find three elements a1 , a2 , a3 and then check if sum-(a1+a2+a3) exists in map. It seems to be O(n^3) or O(n^3 *log n) with map , but it is getting passed within .12 or max .4 seconds. Shouldn't it get TLE verdict when n is 1000. Making O(1000000000).

I would like to know where I am wrong with the calculations.


  Rev. Lang. By When Δ Comment
en3 English Mr_No_One 2020-06-14 15:26:51 17 Tiny change: '.4 seconds for other users . Shouldn'' -> '.4 seconds. Shouldn''
en2 English Mr_No_One 2020-06-14 15:16:25 7 Tiny change: 'link](http://https://cs' -> 'link](https://cs'
en1 English Mr_No_One 2020-06-14 15:14:06 959 Initial revision (published)