Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Time complexity for my palindrome detection algorithm?

Scott Shipp
Ranch Hand
Posts: 223
12
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.

1st call - N
2nd call - N-2
3rd call - N-4
...
(N / 2th-1)th call - 5
N / 2th call - 3

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.

Greg Charles
Sheriff
Posts: 3014
12
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).

Winston Gutkowski
Bartender
Posts: 10573
65
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

Piet Souris
Rancher
Posts: 1943
66
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?

Greetings,
Piet

Scott Shipp
Ranch Hand
Posts: 223
12
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..

Winston Gutkowski
Bartender
Posts: 10573
65
Scott Shipp wrote:Any thoughts?

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 first and last 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.

Winston

Steve Fahlbusch
Bartender
Posts: 605
7
Of Course if you can have a couple of pointers you can easily make this an O(n). Well actually O(3n), but O(n) none the less

 Consider Paul's rocket mass heater.