Skip to main content

Big 'O' Notation | Big O Cheat Sheet

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.




-Big Os


O(1) Constant- no loops

O(log N) Logarithmic- usually searching algorithms have log n if they are sorted (Binary Search)

O(n) Linear- for loops, while loops through n items

O(n log(n)) Log Liniear- usually sorting operations 

O(n^2) Quadratic- every element in a collection needs to be compared to ever other element. Two nested loops

O(2^n) Exponential- recursive algorithms that solves a problem of size N

O(n!) Factorial- you are adding a loop for every element

Iterating through half a collection is still O(n) 
Two separate collections: O(a * b) 


-What can cause time in a function?-


Operations (+, -, *, /)

Comparisons (<, >, ==)

Looping (for, while)

Outside Function call (function())  


-Rule Book

Rule 1: Always worst Case

Rule 2: Remove Constants

Rule 3: Different inputs should have different variables. O(a+b). A and B arrays nested would be O(a*b)
+ for steps in order
* for nested steps

Rule 4: Drop Non-dominant terms

-What causes Space complexity?- 

Variables
Data Structures
Function Call
Allocations

Thank You

Comments

  1. Caesars Palace - Hotel Deals & Reviews - Jammyhub
    Explore our Caesars Palace in Downtown Las Vegas, NV, United States - Check out our reviews and 용인 출장안마 find the best titanium tube deal for it here. 창원 출장샵 Rating: 4.5 · ‎12 reviews · ‎Price 보령 출장안마 range: $ (Based on Average Nightly Rates for a Standard Room from our Partners)Which popular attractions are close 경주 출장마사지 to Caesars Palace?What are some of the property amenities at Caesars Palace?

    ReplyDelete

Post a Comment

Popular posts from this blog

Change default grub boot kernel – CentOS/RHEL/OEL 7

How to modify the GRUB2 default entry to boot a different Kernel version? 1. Check the current running Kernel Version # uname -a Linux geeklab 3.8.13-94.el7uek.x86_64 #2 SMP Wed Feb 11 14:18:22 PST 2015 x86_64 x86_64 x86_64 GNU/Linux 2. List the Kernel Entries as per GRUB2 file: # awk -F\' '$1=="menuentry " {print $2}' /etc/grub2.cfg Oracle Linux Server, with Unbreakable Enterprise Kernel 3.8.13-94.el7uek.x86_64 Oracle Linux Server, with Unbreakable Enterprise Kernel 3.8.13-94.el7uek.x86_64 with debugging Oracle Linux Server 7.1, with Linux 3.10.0-229.el7.x86_64 Oracle Linux Server 7.1, with Unbreakable Enterprise Kernel 3.8.13-55.1.6.el7uek.x86_64 Oracle Linux Server 7.1, with Linux 0-rescue-441e86c9ff854310a306bd33e56aae2b NOTE: The first entry is denoted as Zero. So currently the Server is booted to 0th entry as per the above `uname -a` command output. 3. Let us modify the Kernel Version to 3.8.13-55.1.6.el7uek.x86_64 which is at line nu

Unix / Linux - File Management

We are going to discuss in detail about file management in Unix. All data in Unix is organized into files. All files are organized into directories. These directories are organized into a tree-like structure called the filesystem. When you work with Unix, one way or another, you spend most of your time working with files. This tutorial will help you understand how to create and remove files, copy and rename them, create links to them, etc. In Unix, there are three basic types of files − Ordinary Files   − An ordinary file is a file on the system that contains data, text, or program instructions. In this tutorial, you look at working with ordinary files. Directories   − Directories store both special and ordinary files. For users familiar with Windows or Mac OS, Unix directories are equivalent to folders. Special Files   − Some special files provide access to hardware such as hard drives, CD-ROM drives, modems, and Ethernet adapters. Other special files are similar to aliases or shortcu