Introduction to Complexity Theory

Introduction

Complexity theory is the study of the resources (especially computation time and memory) required by algorithms.

Learning Project Summary

• Project code:
• Suggested Prerequisites:
  • Students should be familiar with the concepts of deterministic and nondeterministic computation, and formal models of computation, such as finite state automata and Turing machines.
  • Students should also be familiar with the theory of formal languages
• Time investment:
• Assessment suggestions:
• School: School of Computer science
• Department: Institute for Complexity Theory
• Stream
• Level:

Goals

The introduction to complexity theory course will offer a comprehensive course in complexity theory .

Course

Subject classification: this is a mathematics resource.

Subject classification: this is an information technology resource.

Educational level: this is a tertiary (university) resource.

Lessons

• Lesson 1—Big O Algorithm Analysis
• Lesson 2—Time Complexity
• Lesson 3—Space Complexity and Savitch's Theorem
• …

Tests and Quizzes

• Quiz 1—Big O Quiz

Active participants

Please sign below if you are participating in this topic. Use 4 tildes (~) to sign.

• Kinkydarkbird 03:35, 5 January 2009 (UTC)