Data-structures 01

Complexity

Algorithm runtime definition

Worst and best cases definition

Average case definition

Example

i = 1                            # 1 time
while i <= n:                    # n+1 times
	if arr[i] == k: return True  # n times
	i += 1                       # n times
return False                     # 1 time
								 # _________
                                 # 3n + 3 in total

Big-O, Omega, “order” of functions definition

Data structures

Array definition

Stack definition

Parenthesis validation

Postfix Polish notation

Queue definition