Input size and basic operation examples Problem Input size measure Basic operation Searching for key in a Number of list's items, Kev comparison list of n items l.e. n Multiplication of two Matrix dimensions or Multiplication of two matrices total number of elements numbers Checking primality of n'size= number of digits Di vIsIon a given integer n (in binary representation) Visiting a vertex or ypical graph problem #vertices and/oredges traversing an edge Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-3 Input size and basic operation examples Problem Input size measure Basic operation Searching for key in a list of n items Number of list’s items, i.e. n Key comparison Multiplication of two matrices Matrix dimensions or total number of elements Multiplication of two numbers Checking primality of a given integer n n’size = number of digits (in binary representation) Division Typical graph problem #vertices and/or edges Visiting a vertex or traversing an edge