-1

I was asked on the best and worst case scenario for this function:

def is_palindromic(the_list):

    result = True 
    the_stack=Stack()
    for item in the_list:
        the_stack.push(item)
    for item in the_list:
        item_stack=the_stack.pop()
        if item != item_stack:
            result = False
    return result

This function determines if a list is the same as its reverse using a stack. I thought the time complexity was the same for every case but when I tested, it took longer to run if the list was indeed the same as its reverse. Can anyone explain why? I am a bit confused.

Ayoub Omari
  • 806
  • 1
  • 7
  • 24
Ana Rita França
  • 1
  • 6
    Complexity is not a measure of time. – molbdnilo Dec 13 '19 at 14:37
  • 1
    Did they tell you which time complexities the Best and Worst case were? – Cedric Dec 13 '19 at 14:40
  • How much longer did it take, what did you compare to, and how did you measure? I would be surprised if you found a *significant* difference with that function. If you were to break out of the loop when you found a difference, I would not be. – molbdnilo Dec 13 '19 at 14:44
  • If I am not mistaken the time complexity in every case is the same. Though you overwrite result in one step if they are indeed the palindrome. So that causes the time delta you are confused about. Especially in Python this can take some time as variables can change types, ... What you can try is to add an else case and reassign the variable every time. Then indeed it should have similar runtime (in ms). – Cedric Dec 13 '19 at 14:45
  • Can you give us the time difference you noticed using timeit or whatever you used – Ayoub Omari Dec 13 '19 at 14:47
  • The only difference is in the number of `result = False`. Since you do this once for every *un*equal element, the palindromic case should be faster, if anything. – molbdnilo Dec 13 '19 at 14:56
  • The difference is less than 1 microsecond but I am testing it with small lists. I was told by my professor that in the best case the function would return after one iteration if the last and first items are different. Is he right? – Ana Rita França Dec 14 '19 at 13:52

2 Answers2

1

Both cases are O(n). You always load up the stack, which should be an O(n) operation. In the best case, the first character does not match the last, so the search should terminate immediately. In the worst case, all the characters match, so the program makes another n pops and comparisons. O(2n) is still O(n).

Keep in mind that the current code makes the same pops and comparisons even after determining that the word is not a palindrome. The line result = False should be return False or at least be followed by a break statement. What makes the worst case run slower is likely that a non-palindromic word will have many mismatches, causing that if block to execute repeatedly to set result to False over and over. This does not alter the complexity because it is a constant time operation.

Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
  • 3
    There is no break when the characters are not the same, she is just modifying the `result ` variable – Ayoub Omari Dec 13 '19 at 14:48
  • @Sarmon. Interesting I read `result =` as return because I was expecting it so much – Mad Physicist Dec 13 '19 at 14:51
  • @Sarmon. Updated – Mad Physicist Dec 13 '19 at 14:56
  • My question is not about optimizing the code. Those changes would indeed improve the function and I appreciate your suggestions. But what I don't understand is why it is taking more time for the function to finish when the list is indeed the same as its reverse, when compared to one that isn't (even when the two lists have the same size). Shouldn't it be the same? My understanding is that the best-case scenario and worst-case scenario are the same as it performs the same pops and comparisons. What am I missing? – Ana Rita França Dec 14 '19 at 13:30
  • @AnaRitaFrança. I've addressed that in my update. In the best case, the body of the `if` does not execute. Worst case, you assign a variable over and over. This takes time. – Mad Physicist Dec 14 '19 at 17:39
  • @MadPhysicist. Ah, right, I did not think about the time of the assignments. It makes sense now. Thank you for your help! – Ana Rita França Dec 15 '19 at 14:38
  • @AnaRitaFrança. You can select an answer even after your question is closed – Mad Physicist Dec 15 '19 at 18:10
0

Since the return statement is only given once and every line before it has to run (no returns or breaks in the loops), the only thing that should affect the timing is the size of the parameter (the_list).

Best case seems to be if it has length 1 or 0. It gets worse as length -> Infinity. Since you do not have any nested loops, it looks like you have an O(n) function, so time would increase proportionally with the n.

I suppose that it is possible to have different processing times based on the contents of the_list as opposed to just the size of the array, but it would be very small.

Tyler H
  • 110
  • 9