How time complexity of DFS is O(V+E) if we use adjacency lists for representing the graphs?

Question

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)

Answer 1

(Note: i am using the stack implementation for easier understanding)

1.Stack stack; // i have named my stack as "stack"
2.isVisited(root) = true;
3.stack.push(root);
4.while(stack is not empty)
5.{
6. currentNode = stack.top();
7. stack.pop();
8. print(currNode); //or whatever operation you want to do!
9. for all each v in adj[currNode]
10 if(!isVisited[v])
11 {
12 stack.push(v);
13 isVisited[v] = true;
14 }
15 }

Now for the analyses part....
Lets break the work done... lets exclude the lines 9-14 for now... Do we agree the work done in while loop excluding lines 9-14 is constant?
Once we have established this fact lets see how many times this loop executes. Simple enough to see that each vertex it added to stack once and hence it executes V times. Thus total work done O(V).

Now lets take line 9-14 part separately.
How many times have the lines 9-14 executed? For each while loop they have been executed same number of times as the elements in the respective vertex's adjacency list. And if you add up all the adjacency lists of all the vertices how many executions you get? O(E).

combining these two separate works done the total work comes out to be O(V) + O(E) = O(V+E)
This is called aggregate analysis. For details refer stackoverflow or the good old Introduction to algorithms by cormen et al.

PS: for understanding purposes I might have been slightly off the mark here or there... but you would be able get the basic idea i guess.

Answer 2

//Program of interpolation search its Complexity is O(log log n)

include "stdio.h"

include "stdlib.h"

define MAX 200

int interpolation_search(int a[], int bottom, int top, int item) {

int mid;
while (bottom <= top) {
mid = bottom + (top - bottom)
* ((item - a[bottom]) / (a[top] - a[bottom]));
if (item == a[mid])
return mid + 1;
if (item < a[mid])
top = mid - 1;
else
bottom = mid + 1;
}
return -1;
}

int main() {
int arr[MAX];
int i, num;
int item, pos;

printf("\nEnter total elements (num< %d) : ", MAX);
scanf("%d", &num);

printf("Enter %d Elements : ", num);
for (i = 0; i < num; i++)
scanf("%d", &arr[i]);

printf("\nELEMENTS ARE\n: ");
for (i = 0; i < num; i++)
printf("%d\t", arr[i]);

printf("\nSearch For : ");
scanf("%d", &item);
pos = interpolation_search(&arr[0], 0, num, item);
if (pos == -1)
printf("\nElement %d not found\n", item);
else
printf("\nElement %d found at position %d\n", item, pos);

return 0;
}