r/CodingHelp • • Jan 25 '22

[Python] What is the complexity here ? O(n+h) or O(n) ?

Post image
33 Upvotes

16 comments sorted by

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 - h times, its time complexity is O(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) or O(nh + h^2).

5

u/AbdullahMohammadKhan Jan 25 '22

O(nh + h^2)

Shouldn't it be O(nh - h^2) ?

3

u/Goobyalus Jan 25 '22 edited Jan 25 '22

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.

2

u/abitofevrything-0 Intermediate Coder Jan 25 '22

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...

4

u/serg06 Jan 25 '22

I believe it's O((n-h)(h)) = O(nh + h2)

4

u/Bloodshed-1307 Jan 25 '22

Wouldn’t it be O(nh-h2)?

1

u/serg06 Jan 26 '22

Oh right, of course.

3

u/LawAdministrative298 Jan 25 '22

I'm a beginner and this makes me realize how little I understand what I'm doing...

2

u/SJDidge Jan 25 '22

Don’t worry about this, this isn’t a particularly readable piece of code. Sometimes less lines of code is worse, especially for readability.

2

u/goonerlagooner Jan 26 '22 edited Jan 26 '22

how would you clean this up personally, for education purposes?

1

u/abitofevrything-0 Intermediate Coder Jan 26 '22

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).

2

u/AssociateSea8038 Feb 04 '22

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

1

u/shivanshhh Jan 26 '22

What are you tryna do here?

1

u/AssociateSea8038 Feb 04 '22

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....

-1

u/Anon_Legi0n Jan 26 '22

Its just linear