AI Features

0% completed

All LessonsFree Lessons (5)

Introduction

The Course C++ Refresher C++ Built-in methods C++ I/O

Complexity Analysis

Algorithm Analysis

Trivial Runtime Analysis

Logarithmic Runtime

Non Trivial Runtime

Amortized Analysis

Comparing Runtimes

Number Theory

Algebra Set Theory Geometry Solved Problem - Factorization Solved Problem - Check Prime Arithmetic Progression (AP)Geometric Progression (GP)Permutations Combinations Solved Problem - PnC Prime Factors Solved Problem - Prime Factorization

Arrays and Vectors

Introduction Vectors Solved Problem - Reverse Subarray Solved Problem - Rotate Array Solved Problem - Merge Sorted Arrays Solved Problem - Subarray Sum

Sieve of Eratosthenes

Sieve of Eratosthenes Implementation Complexity Analysis Solved Problem - Segmented Sieve

Strings

Strings STL Solved Problem - Make String Palindrome Solved Problem - Compare Numbers

Sorting

Introduction Selection Sort Bubble Sort Insertion Sort Merge Sort Quick Sort More on Sorting STL

Linked List

Linked List vs Array Singly Linked List - Searching Singly Linked List - Insertion Singly Linked List - Deletion

Stack

Stack Implementation STL Solved Problem - Balanced Parentheses Sequence

Queue

Queue Implementation STL

Binary Tree

Introduction Types of Binary Trees More on Binary Trees

2 Pointers

Solved Problem - Pair Sum Solved Problem - Triplet Sum

Heap

Heap Implementation Complexity Analysis STL Solved Problem - Kth Largest element Solved Problem - Merge K Sorted Arrays

Binary Search Tree

Binary Search Tree Searching Insertion Traversals Properties Deletion More on BSTs

Balanced Binary Search Tree

Self-Balancing Binary Search Tree Rotation Competitions AVL Tree STL Solved Problem - Sliding Window Maximum

Course Conclusion

Closing Remarks

Competitive Programming in C++: The Keys to Success

Non Trivial Runtime

In this lesson, we'll discuss an example with a non-trivial runtime.

We'll cover the following...

Sum of powers

Sum of powers

Take the code sample below:

for (int i = 1; i <= N; i *= 2)
    for (int j = 1; j <= i; j++)
        x++;

As discussed earlier, the outer loop runs $(logN + 1)$ ...