.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Molly Domino

Efficiency
==========

Objectives
----------

Upon completion of this module, students will be able to:

* Describe Big-O notation and what is meant by time and space Complexity
* Evaluate the complexity of basic algorithms using Big-O notation
* Recognize the impact of dataset size on algorithm efficiency
* Compare algorithm efficiency using Big-O notation
* Discuss the efficiency of Bag Methods

Suggested Reading
~~~~~~~~~~~~~~~~~

Chapter 4 from  `Data Structures and Abstractions with Java, 4th edition  by Frank M. Carrano and Timothy Henry <https://www.amazon.com/Data-Structures-Abstractions-Java-4th/dp/0133744051/ref=sr_1_1?ie=UTF8&qid=1433699101&sr=8-1&keywords=Data+Structures+and+Abstractions+with+Java>`_

Intro to Algorithmic Efficiency [6:07]
--------------------------------------

.. admonition:: Follow Along and Engage

   Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
   
   .. raw:: html
   
      <a href="https://courses.cs.vt.edu/~cs2114/meng-bridge/course-notes/8.4.2-EfficiencyPart1.pdf" target="_blank">
      <img src="https://courses.cs.vt.edu/~cs2114/meng-bridge/images/projector-screen.png" alt="" width="32" height="32">Video Slides 8.4.2-EfficiencyPart1.pdf</img>
      </a>


.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 35%">
         <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=5039bf9c-5160-4264-a439-b400013e3d85&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Intro to Algorithmic Efficiency" aria-description="Intro to Algorithmic Efficiency"></iframe>
      </div>

Checkpoint 1
------------

.. avembed:: Exercises/MengBridgeCourse/EfficiencyCheckpoint1Summ.html ka
   :long_name: Checkpoint 1


Efficiency of Summation Algorithms [14:29]
------------------------------------------

.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 35%">
     <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=699408a7-9098-4f0b-9ca7-b41d0102a95b&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Efficiency of Summation Algorithms" aria-description="Efficiency of Summation Algorithms"></iframe>
  </div>
  
Checkpoint 2
------------

.. avembed:: Exercises/MengBridgeCourse/EfficiencyCheckpoint2Summ.html ka
   :long_name: Checkpoint 2


Efficiency of Bag Methods [7:18]
--------------------------------

.. admonition:: Follow Along and Engage

   Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
   
   .. raw:: html
   
      <a href="https://courses.cs.vt.edu/~cs2114/meng-bridge/course-notes/8.4.4-BagsEfficiency.pdf" target="_blank">
         <img src="https://courses.cs.vt.edu/~cs2114/meng-bridge/images/projector-screen.png" alt="" width="32" height="32">Video Slides 8.4.4-BagsEfficiency.pdf</img>
         </a>



.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 35%">
     <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=a800a51b-211f-402c-a442-b40100f8e817&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Efficiency of Bag Methods" aria-description="Efficiency of Bag Methods"></iframe>
  </div>