#BIG O question

14 messages · Page 1 of 1 (latest)

sterile jungle
#

Hello I was wondering why the time complexity of this function is O(n) even though there is a nested loop:// This function convert a 2-d matrix into a 1-D linear list

Node* flatten(Node* head) {
    if (head == nullptr) {
        return head;
    }

Node* curr = head;
    while (curr != nullptr) {
        // If there's a next row, splice it in.
        if (curr->nextRow != nullptr) {
            Node* nextColNode = curr->next;
            curr->next = curr->nextRow;
            curr->nextRow->prev = curr;
            Node* rowTail = curr->nextRow;
           
            // Find the tail of the next row.
            while (rowTail->next != nullptr) {
                rowTail = rowTail->next;
            }
           
            // Connect tail to the next column node.
            rowTail->next = nextColNode;
            if (nextColNode != nullptr) {
                nextColNode->prev = rowTail;
            }
            curr->nextRow = nullptr;
        }
        curr = curr->next;
    }
    return head;
}

rustic kilnBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

tardy night
#

!f

rustic kilnBOT
# 

Node* flatten(Node* head) {
  if (head == nullptr) {
    return head;
  }

  Node* curr = head;
  while (curr != nullptr) {
    // If there's a next row, splice it in.
    if (curr->nextRow != nullptr) {
      Node* nextColNode = curr->next;
      curr->next = curr->nextRow;
      curr->nextRow->prev = curr;
      Node* rowTail = curr->nextRow;

      // Find the tail of the next row.
      while (rowTail->next != nullptr) {
        rowTail = rowTail->next;
      }

      // Connect tail to the next column node.
      rowTail->next = nextColNode;
      if (nextColNode != nullptr) {
        nextColNode->prev = rowTail;
      }
      curr->nextRow = nullptr;
    }
    curr = curr->next;
  }
  return head;
}
Zelis, Herald of Krill Issues
tardy night
#

@sterile jungle The existance of a nested loop doesn't instantly make something O(n^2), or whatnot. It all depends what the nested loops are doing. You must look at how much work is being done total by the algorithm.

#

This looks like a linked matrix sort of thing?

sterile jungle
#

makes sense, I will review the basics

sterile jungle
tardy night
#

Ultimately all that this is doing is iterating each row, then every node in each row

#

So O(n) in the number of nodes in the whole matrix / the final flattened list, but O(rows * cols) if you think about it as a matrix

sterile jungle
tardy night
#

Happy to help

rustic kilnBOT
#

@sterile jungle Has your question been resolved? If so, run !solved :)

sterile jungle
#

!solved