CppCon 2021 has ended
Back To Schedule
Friday, October 29 • 2:45pm - 3:45pm
Back to Basics: Algorithmic Complexity

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
When you're designing a program, how do you choose appropriate data structures and algorithms? How do you know when the proposed design is likely to be "too slow," without benchmarking the finished code? How can you avoid introducing inefficiencies into the code as you write it, without burning yourself out on "premature optimization"? Why do people always say the inner loop is the most important? How is it that the 10x speedup you committed yesterday was completely wiped out by a mere 2x increase in site traffic today?

In this session, we'll explore the notion of algorithmic complexity, especially as it relates to the data structures and algorithms provided by the C++ standard library, such as std::sort, std::find, and std::binary_search. With just a bit of informal math, we'll define "big-O notation" and demonstrate the differences between complexity classes such as O(1), O(lg n), and O(n). We'll show how to determine the big-O complexity of your own functions by counting loops (including the loops hidden inside STL algorithms and overloaded operators). Then we'll show how we can use limits — or a bit of geometric intuition — to determine that certain algorithms run in linear time despite their complex inner structure, and explain what we mean when we say that vector::push_back runs in "amortized constant time." Finally, we'll discuss ways to trade off space against time, or setup time against query time, and discuss some practical considerations such as constant factors and physical implementation limits.

ALL TALK SESSIONS CAN BE ACCESSED FROM THE MAIN LOBBY: https://cppcon.digital-medium.co.uk/

avatar for Amir Kirsh

Amir Kirsh

Teacher, Dev Advocate, Academic College of Tel-Aviv-Yafo and Incredibuild
Amir Kirsh is a C++ lecturer at the Academic College of Tel-Aviv-Yaffo and a visiting lecturer at Stony Brook University, previously the Chief Programmer at Comverse, after being CTO and VP R&D at a startup acquired by Comverse. He is also a co-organizer of the annual Core C++ conference... Read More →
avatar for Adam Segoli Schubert

Adam Segoli Schubert

Adam is a software consultant, programming instructor, and part of the Dev Advocate office at Incredibuild. He also collaborates on projects which focus on decentralization, parallelization, and blockchain, with the objective of advancing transparency, freely available distributed... Read More →

Friday October 29, 2021 2:45pm - 3:45pm MDT