Understanding Time Complexity in Data Structures and Algorithms

O(log n) - Logarithmic Time :

• Definition: The operation's execution time grows logarithmically with the input size. This usually happens when the problem size is divided in each step.
• Example: Binary search in a sorted array. The array is repeatedly divided in half, leading to a logarithmic time complexity.

O(√n) - Square Root Time :

• Definition: The operation's execution time grows proportionally to the square root of the input size.
• Example: Jump search in a sorted array. Elements are jumped in fixed steps and then a linear search is performed within that range.

O(n) - Linear Time :

• Definition: The operation's execution time grows linearly with the input size.
• Example: Traversing an array. Each element of the array is accessed once, resulting in linear time complexity.

O(n log n) - Linearithmic Time :

• Definition: The operation's execution time grows proportionally to n log n. This is typically seen in algorithms that involve sorting and merging.
• Example: Efficient sorting algorithms like merge sort and quicksort, which divide the array and sort the subarrays.

O(n²) - Quadratic Time :

• Definition: The operation's execution time grows proportionally to the square of the input size.
• Example: Bubble sort and insertion sort. Each element is compared with every other element, leading to a quadratic time complexity.

O(n^c) (where c > 1) - Polynomial Time :

• Definition: The operation's execution time grows proportionally to a polynomial function of the input size.
• Example: Certain dynamic programming algorithms, like those solving the knapsack problem.

O(2^n) - Exponential Time :

• Definition: The operation's execution time grows exponentially with the input size.
• Example: Recursive algorithms for the Fibonacci sequence without memoization. Each call generates two more calls, leading to an exponential growth.

O(n!) - Factorial Time :

• Definition: The operation's execution time grows factorially with the input size.
• Example: Solving the traveling salesman problem using brute force. Every possible permutation of cities is considered, resulting in factorial time complexity.

Note : Here is the image link. so that you can easily understand the topics.

Time Complexity in Arrays, Singly Linked Lists, and Doubly Linked Lists

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 :

• Array: O(n) - Shifting all elements to the right to make space for the new element.
• Singly Linked List: O(1) - The new element is added at the beginning.
• Doubly Linked List: O(1) - Similar to a singly linked list, the new element is added at the beginning.

Insert at Tail :

• Array: O(1) - The new element is added at the end if the array has extra space.
• Singly Linked List: O(1) - The new element is added at the end using a tail pointer.
• Doubly Linked List: O(1) - The new element is added at the end using a tail pointer.

Insert at Any Position :

• Array: O(n) - Elements are shifted to make space for the new element.
• Singly Linked List: O(n) - Traversing the list to reach the desired position and then inserting the new element.
• Doubly Linked List: O(n) - Similar to a singly linked list, traversal is required to reach the desired 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 :

• Array: O(n) - Shifting all elements to the left after removing the first element.
• Singly Linked List: O(1) - The head pointer is moved to the next element.
• Doubly Linked List: O(1) - Similar to a singly linked list, the head pointer is moved to the next element.

Delete at Tail :

• Array: O(1) - The last element is removed directly.
• Singly Linked List: O(n) - Traversing the list to find the second last element and updating its next pointer.
• Doubly Linked List: O(1) - The tail pointer is moved to the previous element.

Delete at Any Position :

• Array: O(n) - Elements are shifted after removing the element at the desired position.
• Singly Linked List: O(n) - Traversing the list to reach the desired position and then removing the element.
• Doubly Linked List: O(n) - Similar to a singly linked list, traversal is required to reach the desired 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.