Trying to get better at determining Big O for a so...

# random

[Colton Idle]

Trying to get better at determining Big O for a solution.

Here's a problem:"Return true if this string is a palindrome"

The solution can be done in O(n). Why is it not O(n/2)?

You can solve it in O(n) by using a pointer on the left and right side. If I use a left and right pointer and at each iteration I move both pointers. Would this not be O(n/2)? Or is this one of those cases where the 2 is a "least irrelevant figure" so I toss it out?

I asked this before and I pretty much got two groups of answers... but one has to be wrong?

So is the answer:
1️⃣ It is O(n/2) but that simplifies to n (get rid of the 2 because it's not significant)
2️⃣ It's not O(n/2). Even though the number of iterations is n/2 you still technically check every index, so it's just O(n)

[Shawn]

Unless someone asks you “What’s the exact T(n) for this particular algorithm”, the point of analyzing an algorithm’s time complexity is to understand how its runtime grows based on n. Whether the actual complexity is O(n) or O(½n) is irrelevant; the trait you’re trying to identify in this instance is the fact that the function’s run time is linearly correlated with n instead of, for example, exponentially or logarithmically correlated.

[Shawn]

Big O is all about describing functions in terms of their growth rate as n approaches infinity. You care about being able to identify the order of the function, rather than being able to write down exactly how long an algorithm will take to complete

[Colton Idle]

I guess what I'm saying here is that I understand both options end up being O(n)

What I don't understand clearly is

Is the answer O(n) because I iterate with a left pointer and right pointer and meet in the middle which is O(n/2) which is O(n)

OR

Is the answer O(n) because I operate on every character in the string once which is O(n)

[Rob Elliot]

It’s O(n) because if you have a String of 10 characters and a String of 100 characters it will take 10 times as long for the second as the first.