CSCE 222 Lecture 3

« previous | Monday, January 24, 2011 | next »

Intro to Ruby

Elementary Operations

• assignment ( = )
• arithmetic ( + - * / % )
• boolean operations ( && || & | ^ ! )
• comparisons ( < <= == >= > )
• indexed (array) access ( [i] )

All have constant running time, i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(1)} time.

Statements

block 1 { }
block 2 { }
block 3 { }
# ...
block k { }

If block k takes $T_{1}$ time, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = T_1 + T_2 + T_3 + ... + T_k} to execute all blocks.

Control Structures

if BoolExpr then
  block 1 { }
else
  block 2 { }
end

If evaluation of BoolExpr takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_B} time and execution of block k takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_K} time, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = O(T_B) + O(\max(T_1, T_2))} to execute if statement.

For Loop

for k in (a..b) do
  block 1 { }
end

If block 1 takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_1(k)} time, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = O(T_1(a)) + O(T_1(a+1)) + ... + O(T_1(b))} for entire for statement.

Function calls

def f( params )
  block 1 { }
end

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_P} is time to assign parameters and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_1(params)} is the time to execute block 1 given params, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = O(T_P + T_1)} for function call.

Example

def bubble_sort(list)      # O(1) params
  list = list.dup      # O(n)
  for i in 0..(list.length - 2) do      # O(n^2) (runs (O(n) n times)
    for j in 0..(list.length - i - 2) do      # O(n) (runs O(1) n times)
      list[j], list[j+1] = list[j+1], list[j] if list[j+1] < list[j]      # O(1)
    end
  end
  return list      # O(!)
end  # O(1) + O(n) + O(n^2) + O(n) + O(1) = O(n^2)