Question about Complexity

So I was solving the “JavaScript Algorithms and Data Structures Projects: Palindrome Checker” challenge and I looked at Solution 3 in freeCodeCamp Challenge Guide: Palindrome Checker , which the author claims to be more optimal than solutions that use methods like toLowerCase(), replace(), split(), reverse(), join().

I’m not sure I understand why using any combination of these functions would be any less optimal than what Solution 3 is doing. Solution 3 is O(n). I looked up the complexity of the aforementioned functions and they’re all O(n). Performing several O(n) functions after each other still gives us a complexity of O(n).

Each call to a function still adds extra time. For the 20 character inputs, probably does not change the time, but if they were say 10,000 or 1 million characters long, you would see some time differences. You would need to set up some tests to confirm this.

Still, O(n + n + … + n) = O(n) , right? In other words the additional complexity would be negligible even for millions of characters

Honestly, each browser will have different times to process the code depending on the internals of the browser’s engine. O(n) is theoretical and not necessarily the reality. But, yes, O(n + n + … + n) == O(n)

1 Like

Like I’m a beginner what is o(n) ,log n what does they really mean in algorithm

Big O (ohh) …

1 Like

remember that time complexity tells you the kind of relation between number of operations and time needed
I am putting random numbers to show, don’t take any of the values here as rappresenting anything
let’s say that the complexity is O(n), it means linear relation between time and number of operations
so a function that could represent the computational time against number of operations could be:

t = 3ms * n

and a second one could be

t = 15ms * n

the time complexity is the same, so for your reasoning they should be equivalent. But one is better than the other.

function 1, with n = 1000 would require 3s, function 2 15s

not only time complexity is important, but actual processing time.

1 Like