Doubt in complexity Analysis | can we solve in O(M*N) time and constant space?

help
, , ,
1

Refer_To_this_problem Flattering Linked List From gfg

Here is my python3 solution.

def merge(first,second):
    dummy=prev=Node(-1)
    while first and second:
        if first.data<=second.data:
            prev.bottom=first
            prev=prev.bottom
            first=first.bottom
        else:
            prev.bottom=second
            prev=prev.bottom
            second=second.bottom
    if first:
        prev.bottom=first
    else:
        prev.bottom=second
    return dummy.bottom
def flatten(root):
  
    curr,nxt=root,root.next
    while nxt:
        temp=nxt
        nxt=nxt.next
        curr=merge(curr,temp)
        
    return curr

approach: tried to merge two lists (vertical) at a time by traversing horizontally. Though the solution is AC this method is O(1) space and
O(M*N^2) time .

    time-complexity analysis: 
    (M+M)+(2M+M)+(3M+M) ..............((N-1)*M+M)=2M+ 3M+(N-1)*M =M(N*(N-1)/2 -1)=O(M*N^2)

HERE ARE MY QUERIES:

  1. is my time complexity analysis correct?
  2. can we solve this problem in O(N*M) time and constant space?