.. 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>`_


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


.. raw:: html

    <center>
    <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_vnmd5r1v' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0"></iframe> 
    </center>
    <br>
    <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/EfficiencyPart1.pdf" target="_blank">
    <img src="../html/_static/Images/projector-screen.png" width="32" height="32">Video Slides EfficiencyPart1.pdf</img>
    </a>

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

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


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


.. raw:: html

     <center>
     <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_aqcczmyk' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0"></iframe> 
     </center>
     

Checkpoint 2
------------

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


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

.. raw:: html

    <center>
    <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_87khvnlc' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0"></iframe> 
    </center>
    
    <br>
    
    <a href="https://courses.cs.vt.edu/cs2114/SWDesignAndDataStructs/course-notes/BagsEfficiency.pdf" target="_blank">
    <img src="../html/_static/Images/projector-screen.png" width="32" height="32">Video Slides BagsEfficiency.pdf</img>
    </a>