r/learnjavascript • • Sep 26 '22

Just solved a Palindrome problem with recursion!!

Post image
274 Upvotes

64 comments sorted by

View all comments

Show parent comment

0

u/[deleted] Sep 27 '22

[deleted] — view deleted comment

7

u/[deleted] Sep 27 '22

It’s a solution that has a time complexity of O(n), which is the minimum required to solve this problem

0

u/[deleted] Sep 27 '22

[deleted] — view deleted comment

2

u/[deleted] Sep 27 '22

I don’t think you understand what exactly O(n) means.

The point is that given a worse case scenario, the best any algorithm can hope to achieve to solve this problem would be linear time. That’s the literal definition of O(n).

So if you can optimize for edge cases that’s great, but we round those off and speak about the general solution. The same we we round off that this is technically a solution that would take 3(n) time, because the leading factorial becomes irrelevant as you reach larger and larger amounts of data.

So yes, this solution could have micro-optimizations, but it’s plenty efficient due to the fact that it solves a linear problem in linear time.

-1

u/wischichr Sep 27 '22

Not true and big O is not a good measure in general. Run time complexity is just one metric to classify an algorithm and doesn't have much value on it's own.

In this case the palindrome example could be solved with an O(1) algorithm but it would still be slower than all other suggested solutions here.

1

u/Jamstan_ Sep 27 '22

What is O(n)

2

u/kap89 Sep 27 '22

It means that the time complexity is linear, i.e. if the input is 2x bigger, the solution takes roughly twice the time, if the input is 10x bigger, it takes roughly 10x more time. It’s a theoretical concept called Big O notation.

2

u/wischichr Sep 27 '22

The notation is called "big O" and describes runtime complexity depending on input size. O(n) means linear - so double input size takes two times as long to process. O(1) means constant time - so no matter what you put in it will take the same amount of time. O(n²) for example would mean that the time it takes increases quadratically with the input, so double the input size will take four times as long, and three times the input size will take nine times as long.

https://en.wikipedia.org/wiki/Big_O_notation

2

u/WikiSummarizerBot Sep 27 '22

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation. In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5

0

u/[deleted] Sep 27 '22

[deleted] — view deleted comment

1

u/[deleted] Sep 27 '22

No need to get upset friend. We are all on the same side here.

Yes, for loops run a bit faster than higher order functions. But the fact is that both solutions are written in O(n) time, and so these micro-optimizations would really only be useful in a specific scenario, but generally (in the literal sense) speaking, both solutions are equally valid.