Can anyone help me calculate the time complexity of this code
https://www.codechef.com/viewsolution/23619643
I think it should give tle but it passes
EDIT: I think it is O(M^2 logN) can somebody confirm…??
I think it has O(n^2)
How? can you explain
since you are using nested loop(time complexity - O(n^2) ) to insert elements into array
because you had nested loops . learn here
@syntaxhacker I know all that stuff. The main time consuming part is the dijkstra and I think it has complexity more than N^2
from google
Your implementation is n^2 .
if you really know all that stuff cant you calculate bro
Its not normal dijkstra guys!!!
There are some adjustments to suit to the question.
I want to know the complexity of this new adjusted dijkstra
even if its not normal just lookin at the code . it has two nested loops so the complexity is N^2 only
Looks like you are new to the cp family
Sometimes it can really be difficult to calculate time complexity
for example ( the one that comes to mind ) try trie and try to calculate complexity
i know its different for different implementation im not such a noobie who cant even calculate time complexity for such easy code . Even im new to cp i could say that N^2 or N^3 ( due to while loop ) by just looking . lets see who says its not and i will watch your expert review about me then.
Actually I think I figured it out.
I think its O(M^2logN)
Can anyone confirm…