complexity The worst-case time complexity of an algorithm A is the running time of A on the worst-case input instance. Cost(A)=max (running time of A on x) input x The worst-case time complexity of a computational problem P is the worst-case complexity of the best algorithm A that solves the problem. the best algorithm that gives right answers on all inputs. Cost(P)=min max (running time of A on x) algorithm Ainput x
complexity ◼ The worst-case time complexity of an algorithm A is the running time of A on the worst-case input instance. ❑ Cost 𝐴 = max input 𝑥 (running time of 𝐴 on 𝑥) ◼ The worst-case time complexity of a computational problem P is the worst-case complexity of the best algorithm A that solves the problem. ❑ the best algorithm that gives right answers on all inputs. ❑ Cost 𝑃 = min algorithm 𝐴 max input 𝑥 (running time of 𝐴 on 𝑥)
Hardness of problems can vary a lot Multiplication: 口1234*5678=？ ■7006652 ▣2749274929483758*4827593028759302=？ Can you finish it in 10 minutes? Do you think you can handle multiplication easily?
Hardness of problems can vary a lot ◼ Multiplication: ❑ 1234 * 5678 = ? ◼ 7006652 ❑ 2749274929483758 * 4827593028759302 = ? ◼ Can you finish it in 10 minutes? ◼ Do you think you can handle multiplication easily?
Complexity of integer multiplication In general,for n-digit integers: X1X2...Xn *y1y2…yn 口x1X2…xn*y1y2…yn=? ★★ [Q]How fast is our algorithm? ■ For each yi (i=n,n-1,...1) we calculate yi *2.xn, n single-digit multiplications n single-digit additions We finally add the n results (with proper shifts) <2n2 single-digit additions. Altogether:4n2 elementary operations single-digit additions/multiplications Multiplication is not very hard even by hand,isn't it?
Complexity of integer multiplication ◼ In general, for 𝑛-digit integers: ❑ 𝑥1𝑥2 …𝑥𝑛 ∗ 𝑦1𝑦2 … 𝑦𝑛 =? ◼ [Q] How fast is our algorithm? ◼ For each 𝑦𝑖 (𝑖 = 𝑛,𝑛 − 1, … , 1) ❑ we calculate 𝑦𝑖 ∗ 𝑥1𝑥2 … 𝑥𝑛, ◼ 𝑛 single-digit multiplications ◼ 𝑛 single-digit additions ◼ We finally add the 𝑛 results (with proper shifts) ◼ ≤ 2𝑛 2 single-digit additions. ◼ Altogether: ≤ 4𝑛 2 elementary operations ❑ single-digit additions/multiplications ◼ Multiplication is not very hard even by hand, isn’t it? 𝑥1𝑥2 … 𝑥𝑛 ∗ 𝑦1𝑦2 … 𝑦𝑛 --------------------------- * * * ∙∙∙ * * * * ∙∙∙ * ∙∙∙ ∙∙∙ + * * * ∙∙∙ * --------------------------------- * * * * * * ∙∙∙ ∙∙∙ *
Inverse problem The problem inverse to Integer Multiplication is Factoring. ■35=？*？ ■437？ ■8633？ It's getting harder and harder, Much harder even with one more digit added! The best known algorithm:running time20(n/)
Inverse problem ◼ The problem inverse to Integer Multiplication is Factoring. ◼ 35 = ? * ? ◼ 437? ◼ 8633? ◼ It’s getting harder and harder, ❑ Much harder even with one more digit added! ◼ The best known algorithm: running time ≈ 2 𝑂(𝑛 1/3)