Big-O Complexity

0.0(0)
studied byStudied by 1 person
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/6

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

7 Terms

1
New cards

Big-O Notation

The growth of functions

Formal mathematical definition:

  • Let T(n) and f(n) be two positive functions from the integers or the real numbers to the real numbers

  • We write T(n) ∊ O(f(n)), and say that T(n) has order of f(n), if there are positive constants M and n₀ such that 

    • T(n) ≤ M×f(n) for all n ≥ n₀

The idea is to establish an upper boundary for the growth of the function T(n) for large n, specified by the function f(n) that is usually much simpler than T(n)

2
New cards

Big O Notation in General

<p></p>
3
New cards

Example Notation

<p></p>
4
New cards

Dominant Terms Examples

<p></p>
5
New cards

Single Loops with O(1) Instructions

<p></p>
6
New cards

Single Loops with O(f(n)) Instructions

<p></p>
7
New cards

Nested Loops

  • Complexity is equal to the number of times innermost statement executed*complexity of statement

  • Complexity of inner loop*complexity of outer loop

  • Care needed if loops are not independent