Big O

Question 1

Definition of Big O

Answer 1

a way to measure how a computer algorithm scale as the amount of data involved increases

Question 2

Does it depend on speed?

Answer 2

No, it depends on how the algorithm scales

Question 3

what do u calculate?

Answer 3

the input the has the greatest effect on the algorithm as it scales

Question 4

O(1)

Answer 4

an algorithm that will execute at the same amount of time regardless the input

Question 5

O(N)

Answer 5

an algorithm that it’s time will grow in direct proportion to the amount of data

Question 6

O(N^2)

Answer 6

the amount of time will be proportional to the square of the amount of data

Question 7

O(LOG N)

Answer 7

the amount of time will decrease by 50% with each iteration

Question 8

Algorithm complexity

Answer 8

is the comparison of two algorithms at an idea level and not at a low lever , not concerning ourselves with language or platform or hardware or CPU because an algorithm running on assembly will be much faster than on python

Question 9

Complexity Analysis

Answer 9

allows us to measure how fast a program runs when it performs a computational task and also allows us to to explain how a program behaves depending on the input

Question 10

Worst Case Analysis

Answer 10

we analyze algorithms considering the worst case meaning we calculate the most unlucky input to output the highest number of instructions

Question 11

Asymptotic behavior

Answer 11

is dropping all constant factors and only keeping the largest growing term

Question 12

What are the names of time complexity O(1) , O(N) , O(N^2) , O(LOG N)

Answer 12

Constant-time algorithm , Linear , Quadratic , Logarithmic

Question 13

how to link between theta and O for explanation

Answer 13

any program that is theta of a is O of b when b is worse than a

Question 14

A Θ( n ) algorithm is O( n )
A Θ( n ) algorithm is O( n2 )
A Θ( n2 ) algorithm is O( n3 )
A Θ( n ) algorithm is O( 1 )
A O( 1 ) algorithm is Θ( 1 )
A O( n ) algorithm is Θ( 1 )

Answer 14

We know that this is true as our original program was Θ( n ). We can achieve O( n ) without altering our program at all.
As n2 is worse than n, this is true.
As n3 is worse than n2, this is true.
As 1 is not worse than n, this is false. If a program takes n instructions asymptotically (a linear number of instructions), we can’t make it worse and have it take only 1 instruction asymptotically (a constant number of instructions).
This is true as the two complexities are the same.
This may or may not be true depending on the algorithm. In the general case it’s false. If an algorithm is Θ( 1 ), then it certainly is O( n ). But if it’s O( n ) then it may not be Θ( 1 ). For example, a Θ( n ) algorithm is O( n ) but not Θ( 1 ).

Question 15

What alternative names to we call theta or O

Answer 15

theta is a tight bound while O is an upper bound

Question 16

Determine which of the following bounds are tight bounds and which are not tight bounds. Check to see if any bounds may be wrong. Use o( notation ) to illustrate the bounds that are not tight.

A Θ( n ) algorithm for which we found a O( n ) upper bound.
A Θ( n2 ) algorithm for which we found a O( n3 ) upper bound.
A Θ( 1 ) algorithm for which we found an O( n ) upper bound.
A Θ( n ) algorithm for which we found an O( 1 ) upper bound.
A Θ( n ) algorithm for which we found an O( 2n ) upper bound.

Answer 16

In this case, the Θ complexity and the O complexity are the same, so the bound is tight.
Here we see that the O complexity is of a larger scale than the Θ complexity so this bound is not tight. Indeed, a bound of O( n2 ) would be a tight one. So we can write that the algorithm is o( n3 ).
Again we see that the O complexity is of a larger scale than the Θ complexity so we have a bound that isn’t tight. A bound of O( 1 ) would be a tight one. So we can point out that the O( n ) bound is not tight by writing it as o( n ).
We must have made a mistake in calculating this bound, as it’s wrong. It’s impossible for a Θ( n ) algorithm to have an upper bound of O( 1 ), as n is a larger complexity than 1. Remember that O gives an upper bound.
This may seem like a bound that is not tight, but this is not actually true. This bound is in fact tight. Recall that the asymptotic behavior of 2n and n are the same, and that O and Θ are only concerned with asymptotic behavior. So we have that O( 2n ) = O( n ) and therefore this bound is tight as the complexity is the same as the Θ.

Question 17

why do we use omega?

Answer 17

to say the our algorithm is a bad one meaning it will never run better than this

Question 18

what is the bound of omega

Answer 18

it’s called a lower bound

Question 19

what is small o and small omega

Answer 19

it’s used to represent the tight bound when theta and O are different then we use small o and when theta and omega are different we represent tight bound with small omega

Question 20

what is a logarithm?

Answer 20

it’s an operation applied to a number that makes it quite smaller

Question 21

how do we calculate logarithm?

Answer 21

by using the base of 2 to the power x so 2^x = 1024

means it’s log(1024)

Question 22

what is the equation to find element using binary search?

Answer 22

in the i’th iteration we arrived at an array size of n / 2^i
which means 1 = n/2^i
2^i = n
log(n)