Info2

0.0(0)

Studied by 0 people

Call Kai

Learn

Practice Test

Spaced Repetition

Match

Flashcards

Knowt Play

Card Sorting

1/6

Earn XP

Info2 FS2026

Last updated 3:07 PM on 5/30/26

Name	Mastery	Learn	Test	Matching	Spaced	Call with Kai

No analytics yet

Send a link to your students to track their progress

New cards

T(n) = a * T(n/b) + f(n)

f(n) = O( n^log_^b⁽^a^{) - ε})

T(n) = Θ( n^log_^b⁽^a⁾ )

New cards

T(n) = a⋅T(n/b) + f(n)

f(n) = Θ( n^log_^b⁽^a⁾)

T(n) = Θ( n^log_^b⁽^a⁾ ⋅ log_b(n) )

New cards

T(n) = a⋅T(n/b) + f(n)

f(n) = O( n^log_^b⁽^a^{) + ε})

a⋅f(n/b) ≤ c⋅f(n) for some c ∈ (0,1)

T(n) = Θ( f(n) )

New cards

MergeSort

Θ( n⋅log₂(n) )

New cards

HeapSort

Θ( n⋅log₂(n) )

New cards

QuickSort

Worst: Θ( n² )
Best: Θ( n⋅log₂(n) )

New cards

Bubble, Selection, InsertionSort

Θ( n² )