백준 2352 이 문제는 한쪽  n개의 포트가 정렬되어있기에 꼬이지 않도록 다른 포트를 최대 한 많이 연결하는 문제로  LIS를 사용하면 쉽게 구할 수 있다는 것을 알게 되었습니다.

근데 시간제한에 맞게 특정한 코드에 대해 시간복잡도를 구하는 과정에서 궁금한게 있습니다.

LIS는 DP와 이분탐색으로 구현할 수 있는데

 DP 를 통해 구현한 경우 시간복잡도O(n*n)이 걸리고 이분탐색을 사용한 경우 단 한번의 다른 포트를 훑어가면 됨으로  O(nlogn)이 걸린다는 것을 알고 있습니다.  

근데 이 시간복잡도를 실제로 문제의 입력과 조건대로 구해봤습니다.  최악의 경우 입력의 n은 40,000이기에 이분탐색을 통한 경우에  40000* 15 번의 연산이 수행되고

 DP를 사용한 경우 40,000 * 40,000의 연산이 수행된다는 것으로 파악 했습니다.제가 어디서 들은게 백준에서 약 10억번의 연산을 수행해야 1초가 지나간다는 것을 어디선가?? 본것 같은데 지금 두개의 계산으로는 이분탐색은 통과고 DP의 경우는 4초? 를 지나서 답을 구하기 때문에 오답이 되는게 맞는 것인가요??