Big(o)

The most wanted even after graduation!

Attempt: To understand in most simplest way. "Layman's language."

• What Big(o) means?

  I want to solve a problem, I want to know how much time is needed to solve it. That's all what Big(o) tells.

• Example:

  O(1): I have one deck of cards with me. Randomly I have placed 6

  cards facing its written part towards me. One of the card in it is 7 of

  spade.

  Task1:Pick up 7 of spade. Whats the Time taken?

  Time: It takes one second to pick up the card. O(1)

  Task2:Pick up any ONE card from it. Whats the Time taken?

  Time: It takes one second to pick one card among it. O(1)

  Task3:All the cards from deck are placed. Pick any ONE card. Whats the

  Time taken?

  Time: It takes one second to pick up any one card from deck. O(1)

  No matter what number of cards is placed (it can be thousand or more ),

  the amount of time taken to pick any one card will always be 1 second

  irrespective of space those cards are covering or quantity of cards.

  O(n): I have one deck of cards with me. Randomly I have placed 6

  cards facing its written part downwards. So, now we dont know what are

  those 6 cards.

  Task1: Search for 2 of hearts. Whats the time taken?

  Time: 2 of hearts may be there or may not be, we dont know. We dont

  know what are those 6 cards. So what will we do? Pick up each card one

  at a time and look for 2 of hearts. This way we are touching all 6 cards

  one time. Time taken is O(6). No matter how many cards are placed we are

  touching each cards atleast one time to find 2 of hearts.

  Task2: 'n' cards are placed, Have to search for Ace of club. What's

  the time taken?

  Time: O(n), Because to find Ace of club, have to pick up each cards

  atleast once.

  O(n^2): I have randomly placed 8 cards such that some card's written

  part is facing upwards and some downwards.

  Task1: Face the cards in the same direction facing upwards. Whats the

  time taken?

  Time: To execute this task we need to visit card 2 times:

  1. Pick up a card and check. It is towards which side.

  2. Now flip the card and check If upwards place as it is, if not turn

  the card and place facing towards upperside.

  Two times an individual card is visited. i.e. O(8^2).

  Same way if 'n' cards are placed and two times we are visiting the

  card individually then the time taken would be O(n^2), which means

  each card is visited 2 times.

• O(n^n): Each n element are visited n times. For eample, there are 26

  cards given, each cards are atleast visited 26 times.

• O(logn): 100 cards are given, check if Joker is present in the

  deck. What's the time taken?

  Task1: To check if Joker is present.

  Time: Searching 100 cards individually is difficult. To search in

  faster and efficient way approach will be:

  1. divide the 100 in two halves.

  2. Search in either one of the halves.

  3. If joker is present, other halv will be discarded.

  4. if joker isn't present, the other half will be divide in two halves

  and repeat the steps 2 and 3 till card is found.

  So, Cards will be divided n times untill Joker is found, thus it will

  be O(logn).