Last updated April 10, 2022

loadStatus: Tags: #archivedCards/cmpt125/bigo Links: Big O Notation

Big O Notation Calculating Time Complexity

Principles

Multiple Inputs

• Attend to all inputs, could be O(ab)

Varying Lengths

Array of strings, sorted each string, then sorted array ?

• Let s be length of longest string
• Let a be length of array
• O(s logs) for sorting strings, then O(a) for sorting array
• Happens

Recursive Calls

• When multiple calls are made, it will most likely be O($branches^{depth}$)
  • ex) If 2 recursive calls, then 2 branches

General Methodology

• Find out how many times it iterates via series 1 + 2 + ... + N
• Combine other relevant things
• Profit

Code Operations

Steps for for loops ?

• find out how the pattern for i
• Assume the stopping condition is met ex. i>=n
• Set i to the pattern found
• Isolate k to find n

• Recurrence Relation Steps for Recursion ?
• Write formula in non-recursion
• Determine stopping condition, when N will become 1
• ex) foo(N/2) will be O(logN)

Recursive T(N-1) is;; O(n)

Recursive T(N/2) is O;; (logN)

Recursion

For Loops

for(i=1;i<n;i=i*2) ?

for (i=n; i>=1; i=i/2) ?

for (i=0; i*i<n; i++) ?

• ii < n is stopping condition, so ii >= n
• $i^2$ = n
• i = $\sqrt{n}$

Explain the process ?

Backlinks

1

list from Big O Notation Calculating Time Complexity AND !outgoing(Big O Notation Calculating Time Complexity)

References:

Created:: 2021-10-19 14:11