Является ли временная сложность этого фрагмента кода O (n)?

Question

struct lists * list_depth[ht]; 
for(int i=0; i<ht; i++) 
    list_depth[i]=NULL; 
insert_to_list(&list_depth[0], root); 
for(int i = 1; i < ht; i++) 
{ 
    struct lists * temp = list_depth[i-1]; 
    while(temp != NULL) 
    { 
     if(temp->node->llink!=NULL) 
      insert_to_list(&list_depth[i],temp->node->llink); 
     if(temp->node->rlink!=NULL) 
      insert_to_list(&list_depth[i],temp->node->rlink); 
     temp = temp->link; 
    } 
} 

Какова временная сложность фрагмента? Поскольку петли вложены, имеет ли она n^2 сложности? Это программа для создания списка элементов на каждой глубине двоичного дерева. Я думаю, что это O (n). Я прав? [N - количество элементов]

Answer 1

Нет, это O (n * log (n)), потому что вы проходите длину дерева, то есть O (log (n)), n раз.