Department

Computer Science

Course Code

CSCA67H3

Professor

Richard Pancer

Running time of Algorithms

Q.What is astep?

Conventions wewill use.

•method call 1+steps to evaluate each argument +steps

to execute method

•return statement 1+steps to evaluate returnvalue

•if statement,while statement (not the entire loop) 1+

steps to evaluate exit condition

•assignment statement 1+steps to evaluate each side

•arithmetic, comparison, boolean operators1+steps to

evaluate each operand

•arrayaccess 1+steps to evaluate index

•member access 2steps

•constants, variables 1step

1

www.notesolution.com

Example.Insertion Sort

Precondition. Ais an arrayof integers.

Postcondition Asorted in non-decreasing order.

IS (int[] A){

int i = 1 // 1: steps

while (i < A.length()){ // 2: steps

t = A[i]; // 3: steps

int j = i; // 4: steps

while (j > 0 && A[j-1] >t){ // 5: steps

A[j] = A[j-1]; // 6: steps

j = j-1; // 7: steps

}

A[j] = t; // 8: steps

i = i+1; // 9: steps

}

}

Notation.

•tIS(A)is the number of steps or time for IS to run on a

speciﬁc input A.

•TIS(n)is the worst case time for anyinput of sizen.

2

www.notesolution.com

Q.Whymight weprefer TIS(n)to tIS(A)?

because it is much more general.

Q.Whymight computing TIS(n)be difﬁcult?

Wehaveto consider all possible inputs of sizen.

Solution. Weﬁnd upper and lower bounds for TIS (n).

Q.What do wemean byan upper bound for TIS (n)?

The max number of steps that the code can make.

Q.What do wemean byalower bound for TIS (n)?

Wewant the maximum number of steps that an input will force.

Note.

•No input can takemore steps than the upper bound.

•Alower bound cannot takeless steps than anyinput.

3

www.notesolution.com

Over 90% improved by at least one letter grade.

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.