Flashcards
Time complexity
Cards in this deck (22)
- 1define a recurrence relationrecursive definition of t(n):
express how the time it takes to solve the problem depends on n but function t(n)'s argument's value is smaller than n - 2t(n) for reversing a linked listt(n)=c+t(n-1)
not recursive:
t(n)=c(n-1) + t(1)
using backwards substitution
t(n) is O(n) - 3t(n) for sorting list by finding the minimum elementt(n) = cn + t(n-1)
using backwards subs:
t(n) = cn(n+1)/2 + t(0)
this is O(n^2) (largest term depends on n^2 - 4t(n) for tower of hanoit(n) = 1+2t(n-1)
or
2^n - 1 since t(1) = 1 - 5t(n) for binary searcht(n) = c + t(n/2)
suppose n is a power of 2
c log2n + t(1)
O(long2n) - 6t(n) for mergesortt(n) = cn + 2t(n/2)
or
cnlog2n + nt(1) when n is a power of 2
O(nlog2n) - 7Suppose the n is a power of 2. When we run mergesort on a list of size n, how many calls f(n) do we make to mergesort?f(n) = 1 + 2f(n/2) = ... = 2n-1
- 8How many recursive calls to merge?n-1
- 9t(n) for quicksortt(n) = cn + t(n-1)
or
t(n) = cn(n+1)/2 + t(0)n
O(n^2) - 10define asymptotically bounded aboveLet t(n) and g(n) be two sequences of integers, where n>=0. We say that t(n) is asymptotically bounded above by g(n) if there exists a positive number n0 such that,
for all n>=n0, t(n)<=g(n).
That is, t(n) becomes less than or equal to g(n) once n becomes sufficiently large. - 11define big OWe say t(n) is O(g(n)) if there exist two positive numbers n0 and c such that, for all n>=n0;
t(n) <= c g(n). - 12define the scaling ruleThe \scaling rule" says that if we multiply a function by a positive constant, then we don't change the O() class of that function.
- 13define the sum ruleThe "sum rule" says that if we have a function that is a sum
of two terms, then the O() class of the function is the larger of the O() classes of the two terms. - 14define the product ruleThe \product rule" says that if we have a function that is the product of two functions, then the O() class of the product function is given by the product of the (simple) functions that represent the O() classes of the original two functions.
- 15define Big Omegaone function grows at least as fast as another function. The lower bound is called "big Omega".
We say that t(n) is [big omega symbol](g(n)) if there exists positive constants n0 and c
such that, for all n>=n0,
t(n)>=c g(n): - 16define Big ThetaWe say that t(n) is [big theta](g(n)) if t(n) is both O(g(n)) and
[big omega](g(n)) for some g(n).
there exists three positive constants n0 and c1 and c2 such that, for all n>=n0,
c1 g(n) <= t(n) <= c2 g(n): - 17tbest and tworst for List Algorithms
- 18limit rule: case 1a
- 19limit rule: case 1b
- 20limit rule: case 2a
- 21limit rule:
- 22limit rule: case 3
Information
- Description
- Computer Science Flashcards on Time complexity, created by Virginie Gagné on 18/04/2022.
- Created by
- Virginie Gagné
- Views
- 0
- Rating