Initializing...
Initializing...
O(log n) - Logarithmic Time :
O(√n) - Square Root Time :
O(n) - Linear Time :
O(n log n) - Linearithmic Time :
O(n²) - Quadratic Time :
O(n^c) (where c > 1) - Polynomial Time :
O(2^n) - Exponential Time :
O(n!) - Factorial Time :
Note : Here is the image link. so that you can easily understand the topics.
Understanding the time complexities of basic operations in different data structures is essential for selecting the appropriate structure for a given task. Let's compare the time complexities for various operations across arrays, singly linked lists, and doubly linked lists:
Insert at Head :
Insert at Tail :
Insert at Any Position :
Singly Linked List Example :
#include <bits/stdc++.h> using namespace std;class Node { public: int value; Node *next;
Node(int value) { this->value = value; this->next = NULL; } };
void insert(Node *head, int position, int value) { Node *newNode = new Node(value); Node *tem = head; for (int i = 0; i < position - 1; i++) { tem = tem->next; } newNode->next = tem->next; tem->next = newNode; }; void insert_at_head(Node *&head, int value) { Node *newNode = new Node(value); newNode->next = head; head = newNode; } void insert_at_tail(Node *&head, Node *&tail, int value) { Node *newNode = new Node(value); if (head == NULL) { head = newNode; tail = newNode; return; } tail->next = newNode; tail = newNode; } int findLength(Node *head) { Node *tem = head; int count = 0; while (tem != NULL) { count++; tem = tem->next; } return count; };
void printLinkedList(Node *head) { Node *tem = head; while (tem != NULL) { cout << tem->value << " "; tem = tem->next; } };
int main() {
Node *head = new Node(10); Node *a = new Node(20); Node *b = new Node(30); Node *c = new Node(40); Node *d = new Node(50); Node *tail = d;
head->next = a; a->next = b; b->next = c; c->next = d;
int position, value; cin >> position >> value;
if (position > findLength(head)) { cout << "Invalid Index" << endl; } else if (position == 0) { insert_at_head(head, value); } else if (position == findLength(head)) { insert_at_tail(head, tail, value); } else { insert(head, position, value); }
printLinkedList(head); return 0; }
Delete at Head :
Delete at Tail :
Delete at Any Position :
Doubly Linked List Example :
#include <bits/stdc++.h> using namespace std;class Node { public: Node *prev; int value; Node *next; Node(int value) { this->prev = NULL; this->value = value; this->next = NULL; } };
void normal_print(Node *head) { Node *temp = head; while (temp != NULL) { cout << temp->value << " "; temp = temp->next; } }
void reverse_print(Node *tail) { Node *temp = tail; while (temp != NULL) { cout << temp->value << " "; temp = temp->prev; } }
void delete_at_position(Node *head, int position) { Node *tem = head; for (int i = 1; i < position - 1; i++) { tem = tem->next; } Node *deleteNode = tem->next; tem->next = tem->next->next; tem->next->prev = tem; delete deleteNode; }
void delete_at_head_position(Node *&head) { Node *deleteNode = head; head = head->next; head->prev = NULL; delete deleteNode; }
void delete_at_tail_position(Node *&tail) { Node *deleteNode = tail; tail = tail->prev; tail->next = NULL; delete deleteNode; }
int find_length(Node *head) { int count = 0; Node *temp = head; while (temp != NULL) { count++; temp = temp->next; } return count; }
int main() { Node *head = new Node(10); Node *a = new Node(20); Node *b = new Node(30); Node *c = new Node(40); Node *tail = c;
head->next = a; a->prev = head; a->next = b; b->prev = a; b->next = c; c->prev = b;
int position; cin >> position;
if (position == 0) { delete_at_head_position(head); } else if (position >= find_length(head)) { delete_at_tail_position(tail); } else { delete_at_position(head, position); }
normal_print(head); cout << endl; reverse_print(tail);
return 0; }
Note : Here is the image link. so that you can easily understand the topics.
By understanding these time complexities, developers can make informed decisions on which data structure to use based on the operations required and their respective efficiencies. This knowledge is fundamental in optimizing code performance and ensuring efficient data management.
Conclusion : Time complexity is a key concept in computer science that significantly impacts the performance of data structures and algorithms. By mastering the different types of time complexities and their implications, developers can write more efficient and effective code. Whether working with arrays, singly linked lists, or doubly linked lists, understanding the time complexities of various operations helps in choosing the right data structure for the task at hand.