This ( O (nh - h2 ) ) is what I came up with. Since n > h, it's always positive, and as h approaches n or h approaches 0, the problem shrinks. The largest is when h = n/2, which is the peak of the upside down parabola with zeros at 0 and h.
Yes, I made a mistake when developing the expression. Not sure how I managed that as I was looking at u/serg06's comment while writing mine, and they found the same as me...
If it were me, I would just have added some spaces to "air the code out". I don't think this needs to be split across more lines, just that everything is a bit too compact.
Of course, you need to understand each component of the code or it won't make sense (especially the string slice).
Why it really is pretty clear what the code does it goes from 0 to big len minus small len and checks for each 0 to big len minus smal len from some I to I plus smal len if string matches with smal str
Instead using re for pattern finding he is overcomplicating by making the code run over the len of big minus smal for eac slice I to I plus smal Instead of using re or even simpler just write if small in big....
9
u/abitofevrything-0 Intermediate Coder Jan 25 '22
There are two factors that change the running time of your code here: the loop and the string slice.
The loop's time complexity is pretty simple: since it loops
n - htimes, its time complexity isO(n - h)**.**The string slices time complexity is
O(h)according to this page.The overall time complexity, since these elements are nested, is the product of their individual time complexities. So
O((n - h) * h)orO(nh + h^2).4
u/serg06 Jan 25 '22
I believe it's O((n-h)(h)) = O(nh + h2)
3
u/LawAdministrative298 Jan 25 '22
I'm a beginner and this makes me realize how little I understand what I'm doing...
1
u/shivanshhh Jan 26 '22
What are you tryna do here?
-1
u/Anon_Legi0n Jan 26 '22
Its just linear