https://[Log in to view URL],C

The Time Complexity of an algorithm/code is not equal to the actual time required 
to execute a particular code, but the number of times a statement executes.

Instead of measuring actual time required in executing each statement in the code,
Time Complexity considers how many times each statement executes. 

Q. Imagine a classroom of 100 students in which you gave your pen to one person.
You have to find that pen without knowing to whom you gave it. 

Here are some ways to find the pen and what the O order is.

O(n2): You go and ask the first person in the class if he has the pen.
Also, you ask this person about the other 99 people in the classroom 
if they have that pen and so on, 
This is what we call O(n2). 

O(n): Going and asking each student individually is O(N).

O(log n): Now I divide the class into two groups, then ask: 
“Is it on the left side, or the right side of the classroom?” 
Then I take that group and divide it into two and ask again, and so on. 
Repeat the process till you are left with one student who has your pen. 
This is what you mean by O(log n). 
I might need to do:

The O(n2) searches if only one student knows on which student the pen is hidden. 
The O(n) if one student had the pen and only they knew it. 
The O(log n) search if all the students knew, but would only tell me if
I guessed the right side. 

O(1):-

#include <stdio.h>
 
int main()
{
    printf("Hello World");
    return 0;
}

Time Complexity: In the above code “Hello World” is printed only once on the screen. 
So, the time complexity is constant: O(1) 
i.e. every time a constant amount of time is required to execute code,
no matter which operating system or which machine configurations you are using. 


O(n):a-

#include <stdio.h>
void main()
{
    int i, n = 8;
    for (i = 1; i <= n; i++) {
        printf("Hello World !!!\n");
    }
}

Time Complexity: In the above code “Hello World !!!” 
is printed only n times on the screen, as the value of n can change. 
So, the time complexity is linear: O(n) i.e. every time,
a linear amount of time is required to execute code.

O(log2(n)):-

#include <stdio.h>
void main()
{
    int i, n = 8;
    for (i = 1; i <= n; i=i*2) {
        printf("Hello World !!!\n");
    }
}
// This code is contributed by Suruchi Kumari
Output
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!

O(log(log n)):-

#include <stdio.h>
#include <math.h>
void main()
{
    int i, n = 8;
    for (i = 2; i <= n; i=pow(i,2)) {
        printf("Hello World !!!\n");
    }
}
// This code is contributed by Suruchi Kumari
Output
Hello World !!!
Hello World !!!



Asymptotic Analysis of Algorithms

lets consider a char letters a-z
loop till i get G
so here the iteration happens till 'G' so 7 itraion goes on till G
the total length of the array is called -> "n" imp or max no of operation to get g

Big-O Notation

if a algoritham has 10 its ok if 1000.. we can not do the same its above limit

O(n+1) is O(n)
O(2n) is O(n)

ex

Char = "a-z"
for(){printf("%d",c)}

then it is called O(n) algorithm because it iterates till last value or n.

input    cost

1	1
100	100
1000	1000

O(log n)
A function whose cost scale logarthmatically with input size and is letts then O(n).

keeps on dividing in half and gets to the result soon as possible

ex

1000 animals from allegrad-zebra find Geraf

so a......z
       o  is the middle one so it cuts all from o..z
then remains a....o then i is middle so cuts from a...i

then i...o remains so its get to girraf in few steps.

input	cost

1	1
10	1
100	3
1000	6

O(n2) n square
A fun thet exhibits quadratic growth relative to input size

ex:

for(){ 100 times
   for(){} 100 times
}
there for it takes 100*100=10000 times.. really big

input	cost

1	1
10	100
1000	1000000
1000000 1e+12

O(nm)
A fun which has 2 inputs that contribute to the growth

A nested loop that iterates over 2 distinct collections of data 

void nm()
for{
	for(){}
}

Relative Timing

Big-O	Elipsed Time

O(1)	1ms
O(log n)6ms
O(n)	16 min
O(nm)	16*m min
O(n2)	11.57 days
O(n3)	3.3 years