CSCI 3160 Design and Analysis of Algorithms Tutorial 1 Chengyu Lin ● ●1
CSCI 3160 Design and Analysis of Algorithms Tutorial 1 Chengyu Lin 1
About me ·Name:Chengyu Lin Email:cylin@cse.cuhk.edu.hk 。Office:SHB117 。○ffice hour:Friday14:00-16:00 You can always send me emails to make appointments ● ●2
About me • Name: Chengyu Lin • Email: cylin@cse.cuhk.edu.hk • Office: SHB 117 • Office hour: Friday 14:00 – 16:00 • You can always send me emails to make appointments 2
Asymptotic Notations 。O(g(n) oBig O o Asymptofic upper bound 2(g(n) o Big Omega o Asymptotic lower bound e(g(n)) o Big Theta o Asymptotic tight bound ● ●3
Asymptotic Notations • O(g(n)) o Big O o Asymptotic upper bound • Ω(g(n)) o Big Omega o Asymptotic lower bound • Θ(g(n)) o Big Theta o Asymptotic tight bound 3
Asymptotic Notations The time (space)complexity of an algorithm usually depends on the input size,where the input could be o verfices/edges of a graph o a sequence of integers Usually the running time of algorithm grows with the input size Usually the running time is written as a function f(n),where n is the input size ● ●4
Asymptotic Notations • The time (space) complexity of an algorithm usually depends on the input size, where the input could be o vertices/edges of a graph o a sequence of integers • Usually the running time of algorithm grows with the input size • Usually the running time is written as a function t(n), where n is the input size 4
Asymptotic Notations Suppose we want to analyze the running time of a program,e.g. for (int i=1;i <n;++i){ for (int j=i;<=n;++j) for (int r 1;r <n;++r){ for (int s =r;s <n;++s){ puts("hello"); 。This takes t(n)=n(n+1)/2·n(n+1)/2= n2(n+1)2/4 steps. Calculating the exact running time is tedious. ●5
Asymptotic Notations • Suppose we want to analyze the running time of a program, e.g. • This takes t(n) = n(n+1)/2 · n(n+1)/2 = n2 (n+1)2/4 steps. • Calculating the exact running time is tedious. for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { for (int r = 1; r <= n; ++r) { for (int s = r; s <= n; ++s) { puts(“hello”); } } } } 5