For fun I am working through some algorithmic problems.

Worked on a problem this week for palindrome detection. Part of the problem is to give the time complexity. I don't know the answer for my implementation. Hoping you guys can clarify for me.

Supposedly this was given in an Amazon interview:

Given a string in the form of a Linked List, check whether the string is palindrome or not. Don’t use extra memory.
Give the time complexity. The node structure is

Spoiler alert: I'm going to tell you how I solved this. But I'm guessing most of you have seen this before....I know I have, in the past. It's a pretty stock problem that gets put into a lot of algorithm books.

The basic idea for my implementation is the two pointer approach. One pointer at the start of the list, one pointer at the end. Compare the two elements. Then move each pointer in towards the middle and do it again, until you hit the middle.

For example "A car, a man, a maraca" (an awesome palindrome):

First time the method is called it compares "A" at the start with "a" at the end. Next "c" of car gets compared with "c" at the end of "maraca." The algorithm recurses toward the middle of the list.

As you can tell from the node structure provided, it's a singly-linked list though so in a poor implementation (not mine) every time a recursive call is made, the two pointers both start at the beginning of the list again and run them through the entire list up to the last value. When the first pointer hits "first" it stays there, but the second pointer continues advancing until it gets to "last."

This means that for N elements, it runs through all N elements, then N-1, then N-2, etc. I believe that is an O(N^2) time complexity.

BUT...

I optimized this by passing a copy of the first pointer into the recursive call. Now I can start one ahead of where I started last time. I don't have to run the pointer through the list from the beginning every time to catch up with where I was.

So here's my question because you guys know your time complexity analysis better than me. Given this algorithm what do you think is the time complexity?

I actually ran a few values into a table.

The poor implementation:
String length, total iterations+recursions
15, 91
17, 116
19, 144
21, 175
23, 209

My implementation:
String length, total iterations+recursions
15, 70
17, 116
19, 108
21, 130
23, 154

Basically it seems like what is happening here is that if N is the length of the string, the recursive method gets called N / 2 times. Inside that method, it iterates through an odd number of elements, that is 2 less each time.

Any thoughts? Let me know if I did not explain myself clearly. I believe this falls into a standard O(log n) "divide and conquer" complexity but I could be wrong and I am really rusty on this.

I'm still seeing O(n^2). To get O(n log n), you have to be recursively breaking the original problem into chunks each with a fraction of the size of the previous recursion, not just a constant amount less. Another way to look at is the sum of 1 .. n is n(n+1)/2, which is better than n^2, but still is O(n^2).

Scott Shipp wrote:Worked on a problem this week for palindrome detection. Part of the problem is to give the time complexity.
...
Given a string in the form of a Linked List, check whether the string is palindrome or not. Don’t use extra memory.

That last constraint is a huge one, and probably needs to be explained in detail because I suspect, if it's taken literally, that there is no solution.

And a recursive solution, even though one may be possible without explicitly defining any extra memory is actually likely to take the most memory of all.

Are you, for example, allowed to define a counter? Or a variable to hold a single character?

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here

The example given "A car, a man, a maraca", isn't a palindrome, because of the spaces and the commas.

My suggestion would be: let's do it the modern way! Create a proper LinkedList and check if
this list is equal to list.reverse()! That would give an O(n) complexity and saves a lot of programming...

But of course Winstons remarks are spot on. Problem with these kind of questions is always: what exactly is allowed?

I came up with the exact formula for the time complexity:

(n-1)/2 * (((n+1)/2) +1)

So essentially (n/2)^2. So yes the Big-O is still O(N^2) although it is miles ahead performance-wise than the "poor implementation" I mentioned.

Winston--I agree but since there was no explanation given about that point on the site where I saw this posted, I decided it must mean not using any external data structure like a hashmap or whatever.

Piet--Generally in my experience palindromes are formed from the letters without the punctuation and the case is ignored. Case in point is the most famous palindrome, "A man, a plan, a canal, Panama!" In my solution I stripped all punctuation / spaces / etc. and lowercased everything before I did the comparison. If someone wants to define "palindrome" differently then the code can be modified to take that into account..

Well, two spring to mind:
1. It doesn't need to be recursive.
2. The first iteration (the one that finds the "last" element) is slightly different from the others, since it can also store the length of the "chain" (N), or the index of the last element, for subsequent iterations to use.
Indeed, if you're allowed to store both firstandlast indices, all subsequent iterations can be done with a
while(++first < --last) loop.

That's why I said that what they mean by "extra memory" is very important.