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. $\Theta (1)$ time.

Statements

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

If block k takes $T_{1}$ time, then $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 $T_{B}$ time and execution of block k takes $T_{K}$ time, then $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 $T_{1}(k)$ time, then $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 $T_{P}$ is time to assign parameters and $T_{1}(params)$ is the time to execute block 1 given params, then $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)