wood burning stoves*
The moose likes Performance and the fly likes Time complexity for my palindrome detection algorithm? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Time complexity for my palindrome detection algorithm?" Watch "Time complexity for my palindrome detection algorithm?" New topic
Author

Time complexity for my palindrome detection algorithm?

Scott Shipp
Ranch Hand

Joined: Mar 31, 2013
Posts: 111
    
    6

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

Joined: Oct 01, 2001
Posts: 2841
    
  11

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

Joined: Mar 17, 2011
Posts: 7552
    
  18

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?
Articles by Winston can be found here
Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 462
    
    6
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

Joined: Mar 31, 2013
Posts: 111
    
    6

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

Joined: Mar 17, 2011
Posts: 7552
    
  18

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

Joined: Sep 18, 2000
Posts: 557
    
    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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Time complexity for my palindrome detection algorithm?
 
Similar Threads
Finding all possible routes in java.
Finding if a Palindrom - Please review
Collection comparable(i)
Comparator
Records are not being saved