Scribd
Upload
52 views10 pages

Algorithms Section 3

The document discusses algorithm performance and time complexity. It defines that time complexity relates the input size n to the time taken to solve a problem. Common time complexities include constant O(1), logarithmic O(log n), linear O(n), log-linear O(n log n), and quadratic O(n^2) time. Big O notation is used to ignore constant factors and analyze asymptotic worst-case time complexity. Examples are provided to demonstrate calculating time complexity of loops and determining overall function complexity.

Uploaded by

mo3azsaif.74
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
52 views10 pages

Algorithms Section 3

The document discusses algorithm performance and time complexity. It defines that time complexity relates the input size n to the time taken to solve a problem. Common time complexities include constant O(1), logarithmic O(log n), linear O(n), log-linear O(n log n), and quadratic O(n^2) time. Big O notation is used to ignore constant factors and analyze asymptotic worst-case time complexity. Examples are provided to demonstrate calculating time complexity of loops and determining overall function complexity.

Uploaded by

mo3azsaif.74
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Algorithms

Section ( 3 )
Algorithm performance
 Algorithm performance : the amount of time and space resources required to execute it.

 Lower execution time = Better performance

Space Complexity Time Complexity


Relation between input size and used Relation between input size and taken
space to solve the problem. time to solve the problem.

 Could measure time, but want performance to be machine independent. Expect to


depend on size of input , Size of input is often called "n”.
MO3AZ
Worst Case
Searching for an element in
array
5 8 1 4 3 9

Best Case Average Worst


First Element Middle
Case LastCase
Element
Elements

Asymptotic Notations : Ignore constant factors and low order terms.


Asymptotic Notation of Worst Case : Big-O Notation.

MO3AZ
Big-O Notation

Big-O Time Example

O( 1 ) Constant X = 5 - Print x - Read x

X O( log(n) ) Logarithmic for( int i = 0 ; i < n ; i/=2 )

O( n ) Linear for( int i = 0 ; i < n ; i++ )


for( int i = 0 ; i < n ; i++ )
X O( n log(n) ) Log-linear
for( int j = 0 ; j > n ; j/=2 )

for( int i = 0 ; i < n ; i++ )


O( n^2 ) Quadratic
for( int j = 0 ; j < n ; j++ )

MO3AZ
Examples

Ignore constant factors and low order


terms
f(n) = 4 O( f(n) ) = O( 1 )

f(n) = 7n + 10

O( f(n) ) = O( n )

f(n) = 4n^2 + n + 12

O( f(n) ) = O( n^2 ) MO3AZ


Rules for calculating repetitions of programming
statements:
- Most statements take constant time = 1 , except for loops and recursion.
X=5 Sum += X Print X Read X
Conditions Statements.
For ( int i = 1 ; i < n ; i++ )
- Loops Rules : Start = 1 - End =
n
1. F(n) = ( End - Start ) + 1= n-1+1=n For ( int i = 1 ; i <= n ; i++ )
Start = 1 - End =
n+1
2. if the loop condition contains a sign (=) , the end is = (n+1-1)+1=n+1
incremented by 1 For ( int i = 1 ; i < n ; i++ ) {
=> n
Print ( i ) ; => n-1
3. Iteration of statements inside the loop} MO3AZ
Examples

Public int sum (int n) { Public int sum(int n){


int i , total; int total;
1 total=n*(n+1)/2 ; 1
total = 0; n+1 1
n Return total;
For( i=1 ; i <= n ; i++ ){ }
F(n) = 1 + 1 = 2 = O( 1 )
total = total1 + i ;
}

F(n) Return
= 1 + ( ntotal
+ 1 ;) + n + 1 = 2n + 3 = O(n)
MO3AZ
Examples

Public int sum() {


int i , total; F(n) = 1 + 21 + 20 + 1 = 43
total = 0 ; 1
O(F(n)) = O( 1 )
for( i = 1 ; i <= 20 ; i++){ 21
20
total = total + i ; Execution time depends on
} 1
the input size , no input in this
code !
Return total ;
} MO3AZ
Compute step execution and big o for the following
code :

X=0; 1

n+3
for( i = -2 ; i < n ;n i++){
+2 F(n) = 1+n+3+n+2+n+2+1= 3n+9
x=x+i; n+2
y=x+2; O(F(n)) = O(n)
} 1

Print(x);

MO3AZ
Compute step execution and big o for the following
code :
int func(a[] ,n ){
int x = 5; 1

for( i = 1 ; i <= n ; i++ ){ n+1

for( j = 1 ; j < n ; j++n )* n F(n) = 1+ n+1+ n*n + n(n-1)+ n(n-1)


= 3n^2 - n + 2
x = x + i + jn ; * ( n – 1 )
print(x) n * ( n – 1 )
O(F(n)) = O( n^2 )
}
}
}
MO3AZ

You might also like