✒️
Computer Science Principles
  • Introduction
  • Overview
  • Course at a Glance
  • Course Exam Description
  • Create Performance Task
  • Reference Sheet
  • Resources
  • Big Idea 1
    • 1.1 Collaboration
    • 1.2 Program Function and Purpose
    • 1.3 Program Design and Development
    • 1.4 Identifying and Correcting Errors
  • Big Idea 2
    • 2.1 Binary Numbers
    • 2.2 Data Compression
    • 2.3 Extracting Information from Data
    • 2.4 Using Programs with Data
  • Big Idea 3
    • 3.1 Variables and Assignments
    • 3.2 Data Abstraction
    • 3.3 Mathematical Expressions
    • 3.4 Strings
    • 3.5 Boolean Expression
    • 3.6 Conditionals
    • 3.7 Nested Conditionals
    • 3.8 Iteration
    • 3.9 Developing Algorithms
    • 3.10 Lists
    • 3.11 Binary Search
    • 3.12 Calling Procedures
    • 3.13 Developing Procedures
    • 3.14 Libraries
    • 3.15 Random Values
    • 3.16 Simulations
    • 3.17 Algorithmic Efficiency
    • 3.18 Undecidable Problems
  • Big Idea 4
    • 4.1 The Internet
    • 4.2 Fault Tolerant
    • 4.3 Parallel and Distributed Computing
  • Big Idea 5
    • 5.1 Beneficial and Harmful Effects
    • 5.2 Digital Divide
    • 5.3 Computing Bias
    • 5.4 Crowdsourcing
    • 5.5 Legal and Ethical Concerns
    • 5.6 Safe Computing
  • Code
    • Week 10
    • Week 11
    • Week 12
    • Week 13
    • Week 14
    • Week 15
    • Week 16
    • Week 17
    • Week 18
    • Week 19
    • Week 20
    • Week 21
    • Week 22
Powered by GitBook
On this page
  • Enduring Understanding
  • Learning Objective
  • Essential Knowledge

Was this helpful?

Export as PDF
  1. Big Idea 3

3.17 Algorithmic Efficiency

Enduring Understanding

There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

Learning Objective

For determining the efficiency of an algorithm:

a. Explain the difference between algorithms that run in reasonable time and those that do not.

b. Identify situations where a heuristic solution may be more appropriate.

Essential Knowledge

A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.

A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the “best” solution among many (e.g., what is the shortest path from A to B?).

Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input.

Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.

An algorithm’s efficiency is determined through formal or mathematical reasoning.

An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.

Different correct algorithms for the same problem can have different efficiencies.

Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.

A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.

Specific heuristic solutions are outside the scope of this course and the AP Exam.

Previous3.16 SimulationsNext3.18 Undecidable Problems

Last updated 1 year ago

Was this helpful?