Time Complexity Analysis

by Aditya Chatterjee, Ue Kiao

This book “Time Complexity Analysis” introduces you to the basics of Time Complexity notations, meaning of the Complexity values and How to analyze various Algorithmic problems. This book includes Time and Space Complexity cheat sheets at the end as a bonus resource.We have tackled several significant problems and demonstrated the approach to analyze them and arrived at the Time and Space Complexity of the problems and Algorithms.This is a MUST-READ book for all Computer Science students and Programmers. Do not miss this opportunity.You will get a better idea to judge which approach will work better and will be able to make better judgements in your development work.See the “Table of content” to get the list of exciting topics you will learn about.Some of the key points you will Access Memory does not take O(1) time. It is complicated and in general, has a Time Complexity of O(√N).Multiplication takes O(N^2) time, but the most optimal Algorithm (developed in 2019) takes O(N logN) time which is believed to be the theoretical limit.As per Time Complexity, finding the largest element and the i-th largest element takes the same order of time.It is recommended that you go through this book twice. First time, you may skip the minute details that you may not understand at first go and get the overview.In the second reading, you will get all the ideas, and this will strengthen your insights.In 1950s, Computing was not a Science.It was a collective effort by several Computer Scientists such as Robert Tarjan and Philippe Flajolet who analyzed several computational problems to demonstrate that Computation Problems are equally complicated as Physics and Mathematics Problems. The ideas captured in this book include some of these analyses which glorified Computer Science and made it a Scientific Time Complexity Analysis Aditya Chatterjee; Ue Kiao, PhD.Contributors (7): Vansh Pratap Singh, Shreya Shah, Vikram Shishupalsingh Bais, Mallika Dey, Siddhant Rao, Shweta Bhardwaj, K. Sai Drishya.Table of Introduction to Time and Space Complexity (+ different notations)2. How to calculate Time Complexity?3. Meaning of different Time Complexity4. Brief Background on NP and P5. Does O(1) time exist?: Cost of accessing Memory6. Time Complexity of Basic Arithmetic Operations6.1. Bitwise operations6.2. Addition6.3. Subtraction6.4. Multiplication6.5. Division7. Analysis of Array8. Analysis of Dynamic Array9. Find largest element10. Find Second largest element11. Find i-th largest element12. Time Complexity Bound for comparison-based sorting12.1. Analysis of Selection Sort12.2. Analysis of Insertion Sort12.3. Analysis of Bubble Sort12.4. Analysis of Quick Sort13. Bound for non-comparison-based sorting13.1. Analysis of Counting Sort13.2. Analysis of Bucket Sort14. Analysis of Linked List15. Analysis of Hash functions16. Analysis of Binary Search17. Time and Space Complexity Cheat SheetsThere is no other book that cover these topics. Many students have several misconceptions which are resolved with the book.Read this book and level up.

179 pages, Kindle Edition

Published September 2, 2021

About the author

Aditya Chatterjee is an Independent Algorithmic Researcher, Software Developer and Technical Author. He is the founding member of OPENGENUS, an organization focused on changing Internet consumption.

Since 1990s, he has been involved, actively, in the growth of Computing in Japan. Major computational advances have been made in the last 3 decades which reformed not only education infrastructure but also the competitive programming community.

He has collaborated with over 500 researchers and has mentored over 3000 learners personally across the Globe through the Internship program at OPENGENUS.