Complexity

complexity of an algo is a measure of possible time or space(memory) that implimentation of an algo needs.So evidently there are two types of complexities defined 1)time complexity 2)space complexity.It is expressed as a function of input variables.

Ex-1:
say this is the code:
s=0; ……step(1)
for i=1 to N
do
s=s+A[i]; …….step(2)
end for

Now lets caluculate time taken,say step(1) needs K1 time step(2) needs K2 time.step(1) is executed only once during the running of the code,where as step(2) being in for loop repeated N times.So total time taken….
f(N)1=K1 + K2*N [footnote]] * represents multiplication throughout in this course [[/footnote]]
this is the time complexity expression for the given code

## classification

1. Θ notation

we say f(N)=Θ(g(N))
if thr xsists constants K1 and K2 s.t. K1*g(N)<=f(N)<= K2*g(N) for all N>N0
Ex-2:
say this is the code:
s=0; ……step(1)
for i=1 to N
for j=1 to N
do
s=s+A[i][j]; …….step(2)
end for
end for

solving it similar to example-1 we get

wrk in progress

[[math label1]]{f(N)}[[/math]]

page revision: 1, last edited: 08 Jun 2007 08:03