chapter 2

Question 1

what dose Analysis of algorithms refers to

Answer 1

determining how “good” an algorithm is, usually in
terms of running time and storage.

Question 2

for what is algorithm analysis

Answer 2

allows you to make quantitative judgments about the value of one algorithm over another

allows you to predict whether the software will meet any efficiency constraints that exist.

Question 2

T or F:

Answer 2

running time and memory are bounded resources

Question 3

What is running time

Answer 3

How long an algorithm needs to produce the output.

Question 4

The running time of an algorithm typically grows with…..

Answer 4

input size

Question 5

Three estimated running time

Answer 5

best,
average and
worst

Question 6

how to analyze an algorithm

Answer 6

in onw of these two ways

1-expermintal study (real code, some typical input test,depends on HW/SW)
2-theoritcal study (all pssiable inputs, indepndent from HW/SW)

Question 7

what is expiermental study in algorithm analysis steps

Answer 7

1 implement the algorithm with code
2 run program diffrent possible input
3 mark up running time with functions in code like clock
4 plot the result

Question 8

Limitations on expiermental study in algorithm analysis

Question 9

some traits of theortical analysis

Answer 9

**Uses a high-level description of the algorithm instead
of an implementation. **

**Represents running time based on the number of
primitive operations or steps executed. **

**Characterizes running time as a function of the input
size, n. **

Question 10

what is primtave operations and give some example of it

Answer 10

**basic computations performed by an algorithm
**
Examples:
Evaluating an expression
Assigning a value to a variable
Indexing into an array
Calling a method
Returning from a method

Question 11

Indexing into an array
Calling a method are examples of

Answer 11

Primitive operations

Question 12

i=1
loop (i<=1000)
application code
i=i+1
end loop

Answer 12

f(n)=1000

Question 13

i=1
loop (i<n)
application code
i=i x 2
end loop

Answer 13

f(n)= log2 n

Question 14

i=1
loop (i<=n)
j=1
loop (j<=n)
application code
j= j +1
end loop
i=i + 1
end loop

Answer 14

f(n)= n2

Question 15

i=1
loop (i<=n)
j=1
loop (j<=n)
application code
j= j *2
end loop
i=i + 1
end loop

Answer 15

f(n)= n log n

Question 16

i=n
loop (i>=1)
application code
i=i / 10
end loop

Answer 16

f(n)= log10 n

Question 17

for (i = 0; i < n; i++)
sum++;
for (j = 1; j <= n; j*=2)
sum++;

Answer 17

f(n)= n + log n

Question 18

i=1
loop (i<=n)
j=1
loop (j<=i)
application code
j= j + 1
end loop
i=i + 1
end loop

Answer 18

f(n)=n [(n+1)/2]

Question 19

for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (a[i][j] == x) return 1 ;
return -1;

Answer 19

f(n)=n.m

Question 20

sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n * n; j++)
sum++;

Answer 20

f(n)= n3

Question 21

assume we have an if statment with each part of the statment having diffrent big o size(eg. if C n times else S stop) how do we determine the big o of this exprssion

Answer 21

whatever is bigger with set it as the big o