Asymptotic Notations
0.0(0)
Studied by 0 people0.0(0)
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt PlayCard Sorting
1/14
Earn XP
Description and Tags
CSCI 163
Last updated 4:47 PM on 1/30/26
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
15 Terms
1
New cards
Summation from (i=1 to n) of (i)
n(n+1)/2
2
New cards
Summation from (i=a to b) of (1)
b-a+1
3
New cards
Summation from (i=0 to n) of (a^i)
(a^(n+1)-1)/(a-1)
4
New cards
Summation from (i=1 to n) of (i²)
n(n + 1)(2n + 1)/6
5
New cards
lim(f(n)/g(n))=L
f(n)=theta(g(n))
6
New cards
lim(f(n)/g(n))=0
f(n)=O(g(n))
7
New cards
lim(f(n)/g(n))=0
f(n)=O(g(n))
8
New cards
lim(f(n)/g(n))=infinity
f(n)=Omega(g(n))
9
New cards
T (n)= T (n− 1) + f (n)
T(n)=T (0) + summation (i=1 to n) f(j)
10
New cards
Master Theorem variable restrictions
a>=1, b>1, d>=0
11
New cards
Master Variable format
T(n)=aT(n/b)+f(n^d)
12
New cards
Master Theorem, a<b^d
theta(n^d)
13
New cards
Master Theorem, a=b^d
theta(n^d*logn)
14
New cards
Master Theorem, a>b^d
theta(n^(logb(a))
15
New cards
Inductive proof steps
Inductive hypothesis, Inductive case (substitute in inductive hypothesis)
Note 
Flashcards (23)