To login with Google, please enable popups

or

Don’t have an account? Sign up

To signup with Google, please enable popups

or

Sign up with Google or Facebook

or

By signing up I agree to StudyBlue's

Terms of Use and Privacy Policy

Already have an account? Log in

Reminder

Edit a Copy

Study these flashcards

- StudyBlue
- United-kingdom
- Loughborough University
- Computer Science
- Computer Science Coc104
- Robert Mercas
- Algorithms 1 - Introduction

Gareth N.

Size:
23
Algorithm

A sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required **output** for any legitimate **input** in a finite amount of time.

The RAM model

- Machine-independent, language-independent generic model of computation
- Operations executed one after another, not concurrently
- Each memory access takes one step.
- Each arithmetic or logical operation, comparison takes one step.
- Each step (basic operation) takes constant time.
- Loops and subroutine calls are not basic operations.

Time Complexity (running time)

Number of basic operations executed (amount of work done), expressed as a function of the size *n* of the problem

Space Complexity

Number of memory cells needed to solve the problem, expressed as a function of the size *n* of the problem*Allows us to measure the amount of space used**with respect to input size*

In-place algorithm

The amount of extra space is constant with respect to the input size

What is the time & space complexity of this:

- Input: A list of n integers a[1], a[2], a[3], . . . , a[n]
- Output: The largest element of the list
- Algorithm (Find max):

- Assign a[1] to a variable max.
- For each element of the list, compare it with max.
- If the element is larger, then update max.

- If assignment takes time c
_{1}, increment takes time c_{2}and comparison takes time c_{3}then the maximum total time is: - c
_{1}n + c_{2}(n − 1) + c_{3}(n − 1) = (c_{1}+ c_{2}+ c_{3})n − (c_{2}+ c_{3}) - RAM Model: as c
_{1}= c_{2}= c_{3}= 1, we have: 3n − 2 time steps - Space: n + 2

Optimal Algorithm

Lower bound for time complexity

Order of magnitude of n functions

Worst case time efficiency - T(*n*)

Average case time efficiency - T_{avg}(*n*)

Best case time efficiency - T_{best}(*n*)

Which has the greater order of growth:

(log n)^{3} or n

Big-O notation *(formal definition)*

What is the Big-O notation for:

n^{3} + n^{2}

What is the Big-O notation for:

2n^{2} + 8n^{2}log n − 3n

Prove that:

2n^{2} + 4n ∈ O(n^{2})

Big-Ω notation: Big-Omega *(formal definition)*

Big-Θ notation: Big-Theta *(formal definition)*

What's the Big-O notation of *O*(*c* · *g*(*n*))?

What's the theorem relating limits to Big notations?

Sign up for free and study better.

Anytime, anywhere.

Get started today!

Find materials for your class:

Download our app to study better. Anytime, anywhere.